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
294
240
272
10
109
163
10
333
2
294
240
272
10
109
163
10
333
3
240
294
272
10
109
163
10
333
4
240
294
272
10
109
163
10
333
5
240
272
294
10
109
163
10
333
6
240
272
294
10
109
163
10
333
7
240
272
10
294
109
163
10
333
8
240
10
272
294
109
163
10
333
9
10
240
272
294
109
163
10
333
10
10
240
272
294
109
163
10
333
11
10
240
272
109
294
163
10
333
12
10
240
109
272
294
163
10
333
13
10
109
240
272
294
163
10
333
14
10
109
240
272
294
163
10
333
15
10
109
240
272
163
294
10
333
16
10
109
240
163
272
294
10
333
17
10
109
163
240
272
294
10
333
18
10
109
163
240
272
294
10
333
19
10
109
163
240
272
10
294
333
20
10
109
163
240
10
272
294
333
21
10
109
163
10
240
272
294
333
22
10
109
10
163
240
272
294
333
23
10
10
109
163
240
272
294
333
24
10
10
109
163
240
272
294
333
25
10
10
109
163
240
272
294
333


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
79
13
181
314
275
254
198
240
2
79
13
181
314
275
254
198
240
3
79
13
181
314
275
254
198
240
4
13
79
181
314
275
254
198
240
5
13
79
181
314
275
254
198
240
6
13
79
181
314
275
254
198
240
7
13
79
181
275
314
254
198
240
8
13
79
181
275
254
314
198
240
9
13
79
181
275
254
198
314
240
10
13
79
181
275
254
198
240
314
11
13
79
181
275
254
198
240
314
12
13
79
181
275
254
198
240
314
13
13
79
181
275
254
198
240
314
14
13
79
181
275
254
198
240
314
15
13
79
181
275
254
198
240
314
16
13
79
181
254
275
198
240
314
17
13
79
181
254
198
275
240
314
18
13
79
181
254
198
240
275
314
19
13
79
181
254
198
240
275
314
20
13
79
181
254
198
240
275
314
21
13
79
181
254
198
240
275
314
22
13
79
181
254
198
240
275
314
23
13
79
181
254
198
240
275
314
24
13
79
181
198
254
240
275
314
25
13
79
181
198
240
254
275
314
26
13
79
181
198
240
254
275
314
27
13
79
181
198
240
254
275
314
28
13
79
181
198
240
254
275
314
29
13
79
181
198
240
254
275
314
30
13
79
181
198
240
254
275
314
31
13
79
181
198
240
254
275
314


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
231
219
77
284
332
289
146
2
353
231
219
77
284
332
289
146
3
353
231
219
77
284
332
289
146
4
146
231
219
77
284
332
289
353
5
146
231
219
77
284
332
289
353
6
146
231
219
77
284
332
289
353
7
146
231
219
77
284
332
289
353
8
146
231
219
77
284
332
289
353
9
146
77
219
231
284
332
289
353
10
146
77
219
231
284
332
289
353
11
146
77
219
231
284
332
289
353
12
146
77
219
231
284
332
289
353
13
146
77
219
231
284
332
289
353
14
77
146
219
231
284
332
289
353
15
77
146
219
231
284
332
289
353
16
77
146
219
231
284
332
289
353
17
77
146
219
231
284
289
332
353
18
77
146
219
231
284
289
332
353
19
77
146
219
231
284
289
332
353
20
77
146
219
231
284
289
332
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
21
152
35
322
264
86
227
150
2
21
152
35
322
264
86
227
150
3
21
152
264
322
35
86
227
150
4
21
152
264
322
35
86
227
150
5
21
322
264
152
35
86
227
150
6
21
322
264
152
35
86
227
150
7
21
322
264
227
35
86
152
150
8
21
322
264
227
35
86
152
150
9
322
21
264
227
35
86
152
150
10
322
21
264
227
35
86
152
150
11
322
264
21
227
35
86
152
150
12
322
264
21
227
35
86
152
150
13
322
264
86
227
35
21
152
150
14
322
264
86
227
35
21
152
150
15
150
264
86
227
35
21
152
322
16
150
264
86
227
35
21
152
322
17
264
150
86
227
35
21
152
322
18
264
150
86
227
35
21
152
322
19
264
227
86
150
35
21
152
322
20
264
227
86
150
35
21
152
322
21
264
227
86
152
35
21
150
322
22
264
227
86
152
35
21
150
322
23
150
227
86
152
35
21
264
322
24
150
227
86
152
35
21
264
322
25
227
150
86
152
35
21
264
322
26
227
150
86
152
35
21
264
322
27
227
152
86
150
35
21
264
322
28
227
152
86
150
35
21
264
322
29
21
152
86
150
35
227
264
322
30
21
152
86
150
35
227
264
322
31
152
21
86
150
35
227
264
322
32
152
21
86
150
35
227
264
322
33
152
150
86
21
35
227
264
322
34
152
150
86
21
35
227
264
322
35
35
150
86
21
152
227
264
322
36
35
150
86
21
152
227
264
322
37
150
35
86
21
152
227
264
322
38
150
35
86
21
152
227
264
322
39
150
86
35
21
152
227
264
322
40
150
86
35
21
152
227
264
322
41
21
86
35
150
152
227
264
322
42
21
86
35
150
152
227
264
322
43
86
21
35
150
152
227
264
322
44
86
21
35
150
152
227
264
322
45
86
35
21
150
152
227
264
322
46
86
35
21
150
152
227
264
322
47
21
35
86
150
152
227
264
322
48
21
35
86
150
152
227
264
322
49
35
21
86
150
152
227
264
322
50
35
21
86
150
152
227
264
322
51
21
35
86
150
152
227
264
322


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
221

119
143
156
182
202
221
263
2
221

119
143
156
182
202
221
263
3
221

119
143
156
182
202
221
263
4
221

119
143
156
182
202
221
263
5
221

119
143
156
182
202
221
263
6
221

119
143
156
182
202
221
263
7
221

119
143
156
182
202
221
263


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
340

13
76
104
107
111
175
241
297
299
301
308
316
340
2
340

13
76
104
107
111
175
241
297
299
301
308
316
340
3
340

13
76
104
107
111
175
241
297
299
301
308
316
340
4
340

13
76
104
107
111
175
241
297
299
301
308
316
340


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!