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
358
51
168
321
70
225
8
261
2
358
51
168
321
70
225
8
261
3
51
358
168
321
70
225
8
261
4
51
358
168
321
70
225
8
261
5
51
168
358
321
70
225
8
261
6
51
168
358
321
70
225
8
261
7
51
168
321
358
70
225
8
261
8
51
168
321
358
70
225
8
261
9
51
168
321
70
358
225
8
261
10
51
168
70
321
358
225
8
261
11
51
70
168
321
358
225
8
261
12
51
70
168
321
358
225
8
261
13
51
70
168
321
225
358
8
261
14
51
70
168
225
321
358
8
261
15
51
70
168
225
321
358
8
261
16
51
70
168
225
321
8
358
261
17
51
70
168
225
8
321
358
261
18
51
70
168
8
225
321
358
261
19
51
70
8
168
225
321
358
261
20
51
8
70
168
225
321
358
261
21
8
51
70
168
225
321
358
261
22
8
51
70
168
225
321
358
261
23
8
51
70
168
225
321
261
358
24
8
51
70
168
225
261
321
358
25
8
51
70
168
225
261
321
358


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
197
339
324
185
294
306
68
132
2
197
339
324
185
294
306
68
132
3
197
339
324
185
294
306
68
132
4
197
339
324
185
294
306
68
132
5
197
324
339
185
294
306
68
132
6
197
324
185
339
294
306
68
132
7
197
324
185
294
339
306
68
132
8
197
324
185
294
306
339
68
132
9
197
324
185
294
306
68
339
132
10
197
324
185
294
306
68
132
339
11
197
324
185
294
306
68
132
339
12
197
324
185
294
306
68
132
339
13
197
324
185
294
306
68
132
339
14
197
185
324
294
306
68
132
339
15
197
185
294
324
306
68
132
339
16
197
185
294
306
324
68
132
339
17
197
185
294
306
68
324
132
339
18
197
185
294
306
68
132
324
339
19
197
185
294
306
68
132
324
339
20
197
185
294
306
68
132
324
339
21
185
197
294
306
68
132
324
339
22
185
197
294
306
68
132
324
339
23
185
197
294
306
68
132
324
339
24
185
197
294
68
306
132
324
339
25
185
197
294
68
132
306
324
339
26
185
197
294
68
132
306
324
339
27
185
197
294
68
132
306
324
339
28
185
197
294
68
132
306
324
339
29
185
197
294
68
132
306
324
339
30
185
197
68
294
132
306
324
339
31
185
197
68
132
294
306
324
339
32
185
197
68
132
294
306
324
339
33
185
197
68
132
294
306
324
339
34
185
197
68
132
294
306
324
339
35
185
68
197
132
294
306
324
339
36
185
68
132
197
294
306
324
339
37
185
68
132
197
294
306
324
339
38
185
68
132
197
294
306
324
339
39
68
185
132
197
294
306
324
339
40
68
132
185
197
294
306
324
339
41
68
132
185
197
294
306
324
339
42
68
132
185
197
294
306
324
339
43
68
132
185
197
294
306
324
339


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
163
191
119
78
312
87
124
281
2
163
191
119
78
312
87
124
281
3
163
191
119
78
312
87
124
281
4
163
191
119
78
281
87
124
312
5
163
191
119
78
281
87
124
312
6
163
191
119
78
281
87
124
312
7
78
191
119
163
281
87
124
312
8
78
191
119
163
281
87
124
312
9
78
191
119
163
281
87
124
312
10
78
191
119
163
124
87
281
312
11
78
191
119
163
124
87
281
312
12
78
191
119
163
124
87
281
312
13
78
87
119
163
124
191
281
312
14
78
87
119
163
124
191
281
312
15
78
87
119
124
163
191
281
312
16
78
87
119
124
163
191
281
312
17
78
87
119
124
163
191
281
312
18
78
87
119
124
163
191
281
312
19
78
87
119
124
163
191
281
312
20
78
87
119
124
163
191
281
312
21
78
87
119
124
163
191
281
312


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
233
358
243
303
30
19
180
332
2
233
358
243
303
30
19
180
332
3
233
358
243
332
30
19
180
303
4
233
358
243
332
30
19
180
303
5
358
233
243
332
30
19
180
303
6
358
233
243
332
30
19
180
303
7
358
332
243
233
30
19
180
303
8
358
332
243
233
30
19
180
303
9
358
332
243
303
30
19
180
233
10
358
332
243
303
30
19
180
233
11
233
332
243
303
30
19
180
358
12
233
332
243
303
30
19
180
358
13
332
233
243
303
30
19
180
358
14
332
233
243
303
30
19
180
358
15
332
303
243
233
30
19
180
358
16
332
303
243
233
30
19
180
358
17
180
303
243
233
30
19
332
358
18
180
303
243
233
30
19
332
358
19
303
180
243
233
30
19
332
358
20
303
180
243
233
30
19
332
358
21
303
243
180
233
30
19
332
358
22
303
243
180
233
30
19
332
358
23
19
243
180
233
30
303
332
358
24
19
243
180
233
30
303
332
358
25
243
19
180
233
30
303
332
358
26
243
19
180
233
30
303
332
358
27
243
233
180
19
30
303
332
358
28
243
233
180
19
30
303
332
358
29
30
233
180
19
243
303
332
358
30
30
233
180
19
243
303
332
358
31
233
30
180
19
243
303
332
358
32
233
30
180
19
243
303
332
358
33
233
180
30
19
243
303
332
358
34
233
180
30
19
243
303
332
358
35
19
180
30
233
243
303
332
358
36
19
180
30
233
243
303
332
358
37
180
19
30
233
243
303
332
358
38
180
19
30
233
243
303
332
358
39
180
30
19
233
243
303
332
358
40
180
30
19
233
243
303
332
358
41
19
30
180
233
243
303
332
358
42
19
30
180
233
243
303
332
358
43
30
19
180
233
243
303
332
358
44
30
19
180
233
243
303
332
358
45
19
30
180
233
243
303
332
358


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
197

47
173
190
197
199
320
344
2
197

47
173
190
197
199
320
344
3
197

47
173
190
197
199
320
344
4
197

47
173
190
197
199
320
344
5
197

47
173
190
197
199
320
344


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
99

77
97
99
132
156
195
196
208
224
245
316
322
350
2
99

77
97
99
132
156
195
196
208
224
245
316
322
350
3
99

77
97
99
132
156
195
196
208
224
245
316
322
350


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!