Algorithms Sorting & Searching
SunshinePHP 2014

Rowan Merewood

Let's start with the
Big
Philosophical Questions

Who am I?

Developer Advocate for Google

                    $social = [
    'blog'     => 'http://merewood.org',
    'facebook' => $this->graphSearch('people i am stalking'),
    'github'   => 'https://github.com/rowan-m',
    'google+'  => 'https://google.com/+RowanMerewood',
    'imdb'     => 'http://imdb.com/name/nm1412348',
    'twitter'  => 'https://twitter.com/rowan_m',
];
                

Why am I here?

  1. Because straight-up, pure computer science is
    AWESOME.
  2. ^EOF


Also, understanding the lower level detail helps you make better use of the higher level abstractions.

Why sort?

  • Displaying lists to humans
  • Categorising data
  • Preparing data for merging
  • Preparing data for searching


In general: to display or to prepare for another operation.

Comparing
Algorithms

Stability

Stable

1
4:A
1:A
1:B
3:A
2:A
3:B
2:B
2:C
2
1:A
1:B
2:A
2:B
2:C
3:A
3:B
4:B

Unstable

1
4:A
1:A
1:B
3:A
2:A
3:B
2:B
2:C
2
1:B
1:A
2:C
2:B
2:A
3:A
3:B
4:B
3
1:A
1:B
2:A
2:B
2:C
3:A
3:B
4:B

Order of unsorted portion maintained

Order of unsorted portion may change

Big O Notation

Rate of growth for resource usage based on the size of its input.

  • Resource usage: CPU cycles / time, memory usage
  • Size of input: number of elements

Big O Notation (cont.)

  • Ο(1): Constant
  • Ο(n): Linear growth
  • Ο(n log n): Logarithmic growth
  • Ο(n2): Quadratic growth

Adaptability

An adaptive algorithm has better performance when the list is already partially sorted

Sorting
Algorithms

Insertion Sort

Code

                    class InsertionSort {
    public function sort(array $elements) {
        $iterations = count($elements);
        for ($index = 1; $index < $iterations; $index++) {
            $elementToInsert = $elements[$index];
            $insertIndex = $index;

            while ($insertIndex > 0 && $elementToInsert < $elements[$insertIndex - 1]) {
                $elements[$insertIndex] = $elements[$insertIndex - 1];
                $elements[$insertIndex - 1] = $elementToInsert;
                $insertIndex--;
            }
        }
        return $elements;
    }
}
                

Insertion Sort (cont.)

Code: Iterate through the list

                    public function sort(array $elements) {
    // At least one iteration per element
    $iterations = count($elements);

    for ($index = 1; $index < $iterations; $index++) {
        // If no other variable operations happen here:
        // algorithm is O(n)
    }
}
                

Insertion Sort (cont.)

Code: Compare elements

                    for ($index = 1; $index < $iterations; $index++) {
    // "Pick up" the current element and its position
    $elementToInsert = $elements[$index];
    $insertIndex = $index;

    // Iterate back through the elements
    // until the correct position it reached
    while ($insertIndex > 0 && $elementToInsert < $elements[$insertIndex - 1]) {
        // Swap out of order elements
        $elements[$insertIndex] = $elements[$insertIndex - 1];
        $elements[$insertIndex - 1] = $elementToInsert;
        $insertIndex--;
    }
}
                

If the list is in order, the while loop is not entered.

Insertion Sort (cont.)

Iterations

1
152
64
294
190
137
269
146
174
2
152
64
294
190
137
269
146
174
3
64
152
294
190
137
269
146
174
4
64
152
294
190
137
269
146
174
5
64
152
294
190
137
269
146
174
6
64
152
190
294
137
269
146
174
7
64
152
190
294
137
269
146
174
8
64
152
190
137
294
269
146
174
9
64
152
137
190
294
269
146
174
10
64
137
152
190
294
269
146
174
11
64
137
152
190
294
269
146
174
12
64
137
152
190
269
294
146
174
13
64
137
152
190
269
294
146
174
14
64
137
152
190
269
146
294
174
15
64
137
152
190
146
269
294
174
16
64
137
152
146
190
269
294
174
17
64
137
146
152
190
269
294
174
18
64
137
146
152
190
269
294
174
19
64
137
146
152
190
269
174
294
20
64
137
146
152
190
174
269
294
21
64
137
146
152
174
190
269
294
22
64
137
146
152
174
190
269
294


Sorted!

Insertion Sort (cont.)

Summary

  • Best case: Ο(n)
  • Average / worst case: Ο(n2)
  • Memory usage: Ο(n)
  • Adaptive, stable, in place, and on line

Bubble Sort

Code

                    class BubbleSort {
    public function sort(array $elements) {
        for ($index = count($elements); $index > 0; $index--) {
            $swapped = false;
            for ($swapIndex = 0; $swapIndex < $index - 1; $swapIndex++) {
                if ($elements[$swapIndex] > $elements[$swapIndex + 1]) {
                    $tmp = $elements[$swapIndex];
                    $elements[$swapIndex] = $elements[$swapIndex + 1];
                    $elements[$swapIndex + 1] = $tmp;
                    $swapped = true;
                }
            }
            if (!$swapped) { return $elements; }
        }
    }
}
                

Bubble Sort (cont.)

Code: Iterate through the list

                    // Iterate through the elements
for ($index = count($elements); $index > 0; $index--) {
    $swapped = false;
    // Swap out of order elements
    // until there's nothing left to swap
    if (!$swapped) { return $elements; }
}
                

Bubble Sort (cont.)

Code

                    for ($index = count($elements); $index > 0; $index--) {
    $swapped = false;
    // Iterate through the unsorted portion of the list
    for ($swapIndex = 0; $swapIndex < $index - 1; $swapIndex++) {
        // Compare and swap elements
        if ($elements[$swapIndex] > $elements[$swapIndex + 1]) {
            $tmp = $elements[$swapIndex];
            $elements[$swapIndex] = $elements[$swapIndex + 1];
            $elements[$swapIndex + 1] = $tmp;
            $swapped = true;
        }
    }
    if (!$swapped) { return $elements; }
}
                

If the list is in order, then $swapped stays false .

Bubble Sort (cont.)

Iterations

1
278
101
217
246
303
22
310
87
2
278
101
217
246
303
22
310
87
3
278
101
217
246
303
22
310
87
4
101
278
217
246
303
22
310
87
5
101
217
278
246
303
22
310
87
6
101
217
246
278
303
22
310
87
7
101
217
246
278
303
22
310
87
8
101
217
246
278
22
303
310
87
9
101
217
246
278
22
303
310
87
10
101
217
246
278
22
303
87
310
11
101
217
246
278
22
303
87
310
12
101
217
246
278
22
303
87
310
13
101
217
246
278
22
303
87
310
14
101
217
246
278
22
303
87
310
15
101
217
246
278
22
303
87
310
16
101
217
246
22
278
303
87
310
17
101
217
246
22
278
303
87
310
18
101
217
246
22
278
87
303
310
19
101
217
246
22
278
87
303
310
20
101
217
246
22
278
87
303
310
21
101
217
246
22
278
87
303
310
22
101
217
246
22
278
87
303
310
23
101
217
22
246
278
87
303
310
24
101
217
22
246
278
87
303
310
25
101
217
22
246
87
278
303
310
26
101
217
22
246
87
278
303
310
27
101
217
22
246
87
278
303
310
28
101
217
22
246
87
278
303
310
29
101
22
217
246
87
278
303
310
30
101
22
217
246
87
278
303
310
31
101
22
217
87
246
278
303
310
32
101
22
217
87
246
278
303
310
33
101
22
217
87
246
278
303
310
34
22
101
217
87
246
278
303
310
35
22
101
217
87
246
278
303
310
36
22
101
87
217
246
278
303
310
37
22
101
87
217
246
278
303
310
38
22
101
87
217
246
278
303
310
39
22
101
87
217
246
278
303
310
40
22
87
101
217
246
278
303
310
41
22
87
101
217
246
278
303
310
42
22
87
101
217
246
278
303
310
43
22
87
101
217
246
278
303
310


Sorted!

Bubble Sort (cont.)

Summary

  • Best case: Ο(n)
  • Average / worst case: Ο(n2)
  • Memory usage: Ο(n)

Bubble Sort (cont.)

The ugly Knuth

The bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems

Quick Sort

Code

                    class QuickSort {
    public function sort(array $elements) {
        $this->doQuickSort($elements, 0, count($elements) - 1);
        return $elements;
    }

    function doQuickSort($elements, $leftIndex, $rightIndex) {
        // Divide the array in two, creating a “pivot” value
        // Move any value lower than the pivot to the left array
        // Move any value higher than the pivot to the right array
        // Recursively repeat the same operation on both arrays
    }
}
                

Quick Sort (cont.)

Code: Create a pivot

                    function doQuickSort($elements, $leftIndex, $rightIndex) {
    // Divide the array in two, creating a “pivot” value
    $pivotIndex = ceil($leftIndex + (($rightIndex - $leftIndex) / 2));
    $pivotElement = $elements[$pivotIndex];
    $leftSwapIndex = $leftIndex;
    $rightSwapIndex = $rightIndex;
    while ($leftSwapIndex <= $rightSwapIndex) {
        // Move the left index until we find an out of order element
        // Move the right index until we find an out of order element
        // Swap them
    }
}
                

Quick Sort (cont.)

Code: Swap values

                    while ($leftSwapIndex <= $rightSwapIndex) {
    // Move the left index until we find an out of order element
    while ($elements[$leftSwapIndex] < $pivotElement) { $leftSwapIndex++; }
    // Move the right index until we find an out of order element
    while ($elements[$rightSwapIndex] > $pivotElement) { $rightSwapIndex--; }
    // Swap them
    if ($leftSwapIndex <= $rightSwapIndex) {
        $tmp = $elements[$leftSwapIndex];
        $elements[$leftSwapIndex] = $elements[$rightSwapIndex];
        $elements[$rightSwapIndex] = $tmp;
        $leftSwapIndex++;
        $rightSwapIndex--;
    }
}
                

Quick Sort (cont.)

Code: Recurse

                    function doQuickSort($elements, $leftIndex, $rightIndex) {
    // Divide the array in two, creating a “pivot” value
    // Move any value lower than the pivot to the left array
    // Move any value higher than the pivot to the right array
    // Recursively repeat the same operation on both arrays
    if ($leftIndex < $rightSwapIndex) {
        $this->doQuickSort($elements, $leftIndex, $rightSwapIndex);
    }
    if ($leftSwapIndex < $rightIndex) {
        $this->doQuickSort($elements, $leftSwapIndex, $rightIndex);
    }
}
                

Quick Sort (cont.)

Iterations

1
353
82
109
228
349
56
248
124
2
353
82
109
228
349
56
248
124
3
353
82
109
228
349
56
248
124
4
124
82
109
228
349
56
248
353
5
124
82
109
228
349
56
248
353
6
124
82
109
228
248
56
349
353
7
124
82
109
228
248
56
349
353
8
124
82
109
228
248
56
349
353
9
124
82
109
56
248
228
349
353
10
124
82
109
56
248
228
349
353
11
124
82
109
56
248
228
349
353
12
56
82
109
124
248
228
349
353
13
56
82
109
124
248
228
349
353
14
56
82
109
124
248
228
349
353
15
56
82
109
124
248
228
349
353
16
56
82
109
124
248
228
349
353
17
56
82
109
124
248
228
349
353
18
56
82
109
124
248
228
349
353
19
56
82
109
124
248
228
349
353
20
56
82
109
124
228
248
349
353
21
56
82
109
124
228
248
349
353
22
56
82
109
124
228
248
349
353
23
56
82
109
124
228
248
349
353


Sorted!

Quick Sort (cont.)

Summary

  • Best / average case: Ο(n log n)
  • Worst case: Ο(n2)
  • Implemented by sort()
  • Easily parallelized

Heap Sort

Code

                    class HeapSort {
    public function sort(array $elements) {
        $size = count($elements);
        for ($index = floor(($size / 2)) - 1; $index >= 0; $index--) {
            $elements = $this->siftDown($elements, $index, $size);
        }
        for ($index = $size - 1; $index >= 1; $index--) {
            $tmp = $elements[0];
            $elements[0] = $elements[$index];
            $elements[$index] = $tmp;
            $elements = $this->siftDown($elements, 0, $index - 1);
        }
        return $elements;
    }
}
                

Heap Sort (cont.)

Code: Sift the heap

                    public function siftDown(array $elements, $root, $bottom) {
    $done = false;
    while (($root * 2 <= $bottom) && (!$done)) {
        if ($root * 2 == $bottom) $maxChild = $root * 2;
        elseif ($elements[$root * 2] > $elements[$root * 2 + 1]) $maxChild = $root * 2;
        else $maxChild = $root * 2 + 1;

        if ($elements[$root] < $elements[$maxChild]) {
            $tmp = $elements[$root];
            $elements[$root] = $elements[$maxChild];
            $elements[$maxChild] = $tmp;
            $root = $maxChild;
        } else
            $done = true;
    }
    return $elements;
}
                

Heap Sort (cont.)

Iterations

1
134
278
342
341
341
42
180
193
2
134
278
342
341
341
42
180
193
3
134
342
278
341
341
42
180
193
4
134
342
278
341
341
42
180
193
5
134
342
341
341
278
42
180
193
6
134
342
341
341
278
42
180
193
7
342
134
341
341
278
42
180
193
8
342
134
341
341
278
42
180
193
9
342
341
341
134
278
42
180
193
10
342
341
341
134
278
42
180
193
11
342
341
341
193
278
42
180
134
12
342
341
341
193
278
42
180
134
13
134
341
341
193
278
42
180
342
14
134
341
341
193
278
42
180
342
15
341
134
341
193
278
42
180
342
16
341
134
341
193
278
42
180
342
17
341
341
134
193
278
42
180
342
18
341
341
134
193
278
42
180
342
19
341
341
278
193
134
42
180
342
20
341
341
278
193
134
42
180
342
21
180
341
278
193
134
42
341
342
22
180
341
278
193
134
42
341
342
23
341
180
278
193
134
42
341
342
24
341
180
278
193
134
42
341
342
25
341
278
180
193
134
42
341
342
26
341
278
180
193
134
42
341
342
27
42
278
180
193
134
341
341
342
28
42
278
180
193
134
341
341
342
29
278
42
180
193
134
341
341
342
30
278
42
180
193
134
341
341
342
31
278
193
180
42
134
341
341
342
32
278
193
180
42
134
341
341
342
33
134
193
180
42
278
341
341
342
34
134
193
180
42
278
341
341
342
35
193
134
180
42
278
341
341
342
36
193
134
180
42
278
341
341
342
37
193
180
134
42
278
341
341
342
38
193
180
134
42
278
341
341
342
39
42
180
134
193
278
341
341
342
40
42
180
134
193
278
341
341
342
41
180
42
134
193
278
341
341
342
42
180
42
134
193
278
341
341
342
43
180
134
42
193
278
341
341
342
44
180
134
42
193
278
341
341
342
45
42
134
180
193
278
341
341
342
46
42
134
180
193
278
341
341
342
47
134
42
180
193
278
341
341
342
48
134
42
180
193
278
341
341
342
49
42
134
180
193
278
341
341
342


Sorted!

Heap Sort (cont.)

Summary

  • Best / average / worst case: Ο(n log n)
  • Implemented by SplMinHeap()
                    $h = new SplMinHeap();
foreach ($unsorted as $val) $h->insert($val);
$h->top();
while($h->valid()) {
    echo $h->current()."\n";
    $h->next();
}
                

Searching Algorithms

Sequential Search

Code

                    class SequentialSearch {
    public function search($target, array $elements) {
        $iterations = count($elements);

        for($index = 0; $index <= $iterations; $index++) {
            if ($target == $elements[$index]) {
                $this->notifyObservers(array($index));
                return true;
            }
        }

        return false;
    }
}
                

Sequential Search (cont.)

Iterations

1
129

0
75
129
154
328
339
350
2
129

0
75
129
154
328
339
350
3
129

0
75
129
154
328
339
350
4
129

0
75
129
154
328
339
350


Found you!

Sequential Search (cont.)

Summary

  • Best case: Ο(1)
  • Average / Worst case: Ο(n)
  • Not as pointless as it looks...

Binary Search

Code

                    class BinarySearch {
    public function search($target, array $elements) {
        return $this->doBinarySearch($target, $elements, 0, count($elements));
    }

    public function doBinarySearch($target, array $elements, $minIndex, $maxIndex) {
        if ($maxIndex < $minIndex) { return false; }
        $midIndex = floor(($minIndex + $maxIndex) / 2);
        if ($elements[$midIndex] > $target) {
            return $this->doBinarySearch($target, $elements, $minIndex, $midIndex - 1);
        }
        if ($elements[$midIndex] < $target) {
            return $this->doBinarySearch($target, $elements, $midIndex + 1, $maxIndex);
        }
        return true;
    }
}
                

Binary Search (cont.)

Iterations

1
9

4
9
47
115
155
185
207
219
243
277
277
330
344
2
9

4
9
47
115
155
185
207
219
243
277
277
330
344
3
9

4
9
47
115
155
185
207
219
243
277
277
330
344
4
9

4
9
47
115
155
185
207
219
243
277
277
330
344
5
9

4
9
47
115
155
185
207
219
243
277
277
330
344


Found you!

Binary Search (cont.)

Summary

  • Best case: Ο(1)
  • Average / Worst case: Ο(log n)
  • Switch to linear search for smaller partitions

Summing up

History

  • Insertion Sort: optimised in 1959 (Shell Sort)
  • Bubble Sort: improved in 1980 (Comb Sort)
  • Quick Sort: developed in 1960 (C. A. R. Hoare)
  • Heap Sort: improved in the '60s (Robert Floyd)


Oh, and there's Radix Sort used by Herman Hollerith in 1887

Thank you!

joind.in/10706
github.com/rowan-m/algo-review-sort
algo-review-sort.appspot.com

Share and enjoy!


  Share!