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
182
114
168
60
325
349
115
171
2
182
114
168
60
325
349
115
171
3
114
182
168
60
325
349
115
171
4
114
182
168
60
325
349
115
171
5
114
168
182
60
325
349
115
171
6
114
168
182
60
325
349
115
171
7
114
168
60
182
325
349
115
171
8
114
60
168
182
325
349
115
171
9
60
114
168
182
325
349
115
171
10
60
114
168
182
325
349
115
171
11
60
114
168
182
325
349
115
171
12
60
114
168
182
325
349
115
171
13
60
114
168
182
325
115
349
171
14
60
114
168
182
115
325
349
171
15
60
114
168
115
182
325
349
171
16
60
114
115
168
182
325
349
171
17
60
114
115
168
182
325
349
171
18
60
114
115
168
182
325
171
349
19
60
114
115
168
182
171
325
349
20
60
114
115
168
171
182
325
349
21
60
114
115
168
171
182
325
349


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
38
194
172
299
356
120
278
285
2
38
194
172
299
356
120
278
285
3
38
194
172
299
356
120
278
285
4
38
194
172
299
356
120
278
285
5
38
172
194
299
356
120
278
285
6
38
172
194
299
356
120
278
285
7
38
172
194
299
356
120
278
285
8
38
172
194
299
120
356
278
285
9
38
172
194
299
120
278
356
285
10
38
172
194
299
120
278
285
356
11
38
172
194
299
120
278
285
356
12
38
172
194
299
120
278
285
356
13
38
172
194
299
120
278
285
356
14
38
172
194
299
120
278
285
356
15
38
172
194
299
120
278
285
356
16
38
172
194
120
299
278
285
356
17
38
172
194
120
278
299
285
356
18
38
172
194
120
278
285
299
356
19
38
172
194
120
278
285
299
356
20
38
172
194
120
278
285
299
356
21
38
172
194
120
278
285
299
356
22
38
172
194
120
278
285
299
356
23
38
172
120
194
278
285
299
356
24
38
172
120
194
278
285
299
356
25
38
172
120
194
278
285
299
356
26
38
172
120
194
278
285
299
356
27
38
172
120
194
278
285
299
356
28
38
172
120
194
278
285
299
356
29
38
120
172
194
278
285
299
356
30
38
120
172
194
278
285
299
356
31
38
120
172
194
278
285
299
356
32
38
120
172
194
278
285
299
356
33
38
120
172
194
278
285
299
356
34
38
120
172
194
278
285
299
356
35
38
120
172
194
278
285
299
356
36
38
120
172
194
278
285
299
356


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
23
357
210
352
267
176
47
205
2
23
357
210
352
267
176
47
205
3
23
357
210
352
267
176
47
205
4
23
205
210
352
267
176
47
357
5
23
205
210
352
267
176
47
357
6
23
205
210
47
267
176
352
357
7
23
205
210
47
267
176
352
357
8
23
205
210
47
176
267
352
357
9
23
205
210
47
176
267
352
357
10
23
205
210
47
176
267
352
357
11
23
205
176
47
210
267
352
357
12
23
205
176
47
210
267
352
357
13
23
205
176
47
210
267
352
357
14
23
47
176
205
210
267
352
357
15
23
47
176
205
210
267
352
357
16
23
47
176
205
210
267
352
357
17
23
47
176
205
210
267
352
357
18
23
47
176
205
210
267
352
357
19
23
47
176
205
210
267
352
357
20
23
47
176
205
210
267
352
357
21
23
47
176
205
210
267
352
357
22
23
47
176
205
210
267
352
357


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
247
50
101
186
156
330
208
166
2
247
50
101
186
156
330
208
166
3
247
50
101
208
156
330
186
166
4
247
50
101
208
156
330
186
166
5
247
50
330
208
156
101
186
166
6
247
50
330
208
156
101
186
166
7
247
330
50
208
156
101
186
166
8
247
330
50
208
156
101
186
166
9
247
330
156
208
50
101
186
166
10
247
330
156
208
50
101
186
166
11
330
247
156
208
50
101
186
166
12
330
247
156
208
50
101
186
166
13
166
247
156
208
50
101
186
330
14
166
247
156
208
50
101
186
330
15
247
166
156
208
50
101
186
330
16
247
166
156
208
50
101
186
330
17
247
208
156
166
50
101
186
330
18
247
208
156
166
50
101
186
330
19
247
208
156
186
50
101
166
330
20
247
208
156
186
50
101
166
330
21
166
208
156
186
50
101
247
330
22
166
208
156
186
50
101
247
330
23
208
166
156
186
50
101
247
330
24
208
166
156
186
50
101
247
330
25
208
186
156
166
50
101
247
330
26
208
186
156
166
50
101
247
330
27
101
186
156
166
50
208
247
330
28
101
186
156
166
50
208
247
330
29
186
101
156
166
50
208
247
330
30
186
101
156
166
50
208
247
330
31
186
166
156
101
50
208
247
330
32
186
166
156
101
50
208
247
330
33
50
166
156
101
186
208
247
330
34
50
166
156
101
186
208
247
330
35
166
50
156
101
186
208
247
330
36
166
50
156
101
186
208
247
330
37
166
156
50
101
186
208
247
330
38
166
156
50
101
186
208
247
330
39
101
156
50
166
186
208
247
330
40
101
156
50
166
186
208
247
330
41
156
101
50
166
186
208
247
330
42
156
101
50
166
186
208
247
330
43
50
101
156
166
186
208
247
330
44
50
101
156
166
186
208
247
330
45
101
50
156
166
186
208
247
330
46
101
50
156
166
186
208
247
330
47
50
101
156
166
186
208
247
330


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
192

157
192
239
269
323
344
359
2
192

157
192
239
269
323
344
359
3
192

157
192
239
269
323
344
359


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
213

37
88
102
125
192
197
213
217
243
276
303
339
360
2
213

37
88
102
125
192
197
213
217
243
276
303
339
360


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!