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
75
151
197
308
51
6
18
114
2
75
151
197
308
51
6
18
114
3
75
151
197
308
51
6
18
114
4
75
151
197
308
51
6
18
114
5
75
151
197
308
51
6
18
114
6
75
151
197
51
308
6
18
114
7
75
151
51
197
308
6
18
114
8
75
51
151
197
308
6
18
114
9
51
75
151
197
308
6
18
114
10
51
75
151
197
308
6
18
114
11
51
75
151
197
6
308
18
114
12
51
75
151
6
197
308
18
114
13
51
75
6
151
197
308
18
114
14
51
6
75
151
197
308
18
114
15
6
51
75
151
197
308
18
114
16
6
51
75
151
197
308
18
114
17
6
51
75
151
197
18
308
114
18
6
51
75
151
18
197
308
114
19
6
51
75
18
151
197
308
114
20
6
51
18
75
151
197
308
114
21
6
18
51
75
151
197
308
114
22
6
18
51
75
151
197
308
114
23
6
18
51
75
151
197
114
308
24
6
18
51
75
151
114
197
308
25
6
18
51
75
114
151
197
308
26
6
18
51
75
114
151
197
308


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
208
216
170
249
197
184
257
112
2
208
216
170
249
197
184
257
112
3
208
216
170
249
197
184
257
112
4
208
216
170
249
197
184
257
112
5
208
170
216
249
197
184
257
112
6
208
170
216
249
197
184
257
112
7
208
170
216
197
249
184
257
112
8
208
170
216
197
184
249
257
112
9
208
170
216
197
184
249
257
112
10
208
170
216
197
184
249
112
257
11
208
170
216
197
184
249
112
257
12
208
170
216
197
184
249
112
257
13
170
208
216
197
184
249
112
257
14
170
208
216
197
184
249
112
257
15
170
208
197
216
184
249
112
257
16
170
208
197
184
216
249
112
257
17
170
208
197
184
216
249
112
257
18
170
208
197
184
216
112
249
257
19
170
208
197
184
216
112
249
257
20
170
208
197
184
216
112
249
257
21
170
208
197
184
216
112
249
257
22
170
197
208
184
216
112
249
257
23
170
197
184
208
216
112
249
257
24
170
197
184
208
216
112
249
257
25
170
197
184
208
112
216
249
257
26
170
197
184
208
112
216
249
257
27
170
197
184
208
112
216
249
257
28
170
197
184
208
112
216
249
257
29
170
184
197
208
112
216
249
257
30
170
184
197
208
112
216
249
257
31
170
184
197
112
208
216
249
257
32
170
184
197
112
208
216
249
257
33
170
184
197
112
208
216
249
257
34
170
184
197
112
208
216
249
257
35
170
184
197
112
208
216
249
257
36
170
184
112
197
208
216
249
257
37
170
184
112
197
208
216
249
257
38
170
184
112
197
208
216
249
257
39
170
184
112
197
208
216
249
257
40
170
112
184
197
208
216
249
257
41
170
112
184
197
208
216
249
257
42
170
112
184
197
208
216
249
257
43
112
170
184
197
208
216
249
257
44
112
170
184
197
208
216
249
257
45
112
170
184
197
208
216
249
257


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
346
281
84
240
313
190
295
264
2
346
281
84
240
313
190
295
264
3
346
281
84
240
313
190
295
264
4
264
281
84
240
313
190
295
346
5
264
281
84
240
313
190
295
346
6
264
281
84
240
295
190
313
346
7
264
281
84
240
295
190
313
346
8
264
281
84
240
295
190
313
346
9
190
281
84
240
295
264
313
346
10
190
281
84
240
295
264
313
346
11
190
240
84
281
295
264
313
346
12
190
240
84
281
295
264
313
346
13
190
240
84
281
295
264
313
346
14
190
84
240
281
295
264
313
346
15
190
84
240
281
295
264
313
346
16
190
84
240
281
295
264
313
346
17
84
190
240
281
295
264
313
346
18
84
190
240
281
295
264
313
346
19
84
190
240
281
295
264
313
346
20
84
190
240
281
264
295
313
346
21
84
190
240
281
264
295
313
346
22
84
190
240
281
264
295
313
346
23
84
190
240
264
281
295
313
346
24
84
190
240
264
281
295
313
346
25
84
190
240
264
281
295
313
346
26
84
190
240
264
281
295
313
346


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
283
137
250
117
152
175
35
39
2
283
137
250
117
152
175
35
39
3
283
250
137
117
152
175
35
39
4
283
250
137
117
152
175
35
39
5
283
250
175
117
152
137
35
39
6
283
250
175
117
152
137
35
39
7
39
250
175
117
152
137
35
283
8
39
250
175
117
152
137
35
283
9
250
39
175
117
152
137
35
283
10
250
39
175
117
152
137
35
283
11
250
175
39
117
152
137
35
283
12
250
175
39
117
152
137
35
283
13
250
175
152
117
39
137
35
283
14
250
175
152
117
39
137
35
283
15
35
175
152
117
39
137
250
283
16
35
175
152
117
39
137
250
283
17
175
35
152
117
39
137
250
283
18
175
35
152
117
39
137
250
283
19
175
152
35
117
39
137
250
283
20
175
152
35
117
39
137
250
283
21
175
152
137
117
39
35
250
283
22
175
152
137
117
39
35
250
283
23
35
152
137
117
39
175
250
283
24
35
152
137
117
39
175
250
283
25
152
35
137
117
39
175
250
283
26
152
35
137
117
39
175
250
283
27
152
137
35
117
39
175
250
283
28
152
137
35
117
39
175
250
283
29
152
137
39
117
35
175
250
283
30
152
137
39
117
35
175
250
283
31
35
137
39
117
152
175
250
283
32
35
137
39
117
152
175
250
283
33
137
35
39
117
152
175
250
283
34
137
35
39
117
152
175
250
283
35
137
117
39
35
152
175
250
283
36
137
117
39
35
152
175
250
283
37
35
117
39
137
152
175
250
283
38
35
117
39
137
152
175
250
283
39
117
35
39
137
152
175
250
283
40
117
35
39
137
152
175
250
283
41
117
39
35
137
152
175
250
283
42
117
39
35
137
152
175
250
283
43
35
39
117
137
152
175
250
283
44
35
39
117
137
152
175
250
283
45
39
35
117
137
152
175
250
283
46
39
35
117
137
152
175
250
283
47
35
39
117
137
152
175
250
283


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
112

16
46
65
112
166
265
304
2
112

16
46
65
112
166
265
304
3
112

16
46
65
112
166
265
304
4
112

16
46
65
112
166
265
304
5
112

16
46
65
112
166
265
304


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
147

6
88
92
116
127
147
154
168
177
218
312
333
355
2
147

6
88
92
116
127
147
154
168
177
218
312
333
355
3
147

6
88
92
116
127
147
154
168
177
218
312
333
355
4
147

6
88
92
116
127
147
154
168
177
218
312
333
355
5
147

6
88
92
116
127
147
154
168
177
218
312
333
355


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!