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
169
71
236
325
262
110
95
255
2
169
71
236
325
262
110
95
255
3
71
169
236
325
262
110
95
255
4
71
169
236
325
262
110
95
255
5
71
169
236
325
262
110
95
255
6
71
169
236
325
262
110
95
255
7
71
169
236
262
325
110
95
255
8
71
169
236
262
325
110
95
255
9
71
169
236
262
110
325
95
255
10
71
169
236
110
262
325
95
255
11
71
169
110
236
262
325
95
255
12
71
110
169
236
262
325
95
255
13
71
110
169
236
262
325
95
255
14
71
110
169
236
262
95
325
255
15
71
110
169
236
95
262
325
255
16
71
110
169
95
236
262
325
255
17
71
110
95
169
236
262
325
255
18
71
95
110
169
236
262
325
255
19
71
95
110
169
236
262
325
255
20
71
95
110
169
236
262
255
325
21
71
95
110
169
236
255
262
325
22
71
95
110
169
236
255
262
325


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
263
118
16
200
110
139
281
122
2
263
118
16
200
110
139
281
122
3
263
118
16
200
110
139
281
122
4
118
263
16
200
110
139
281
122
5
118
16
263
200
110
139
281
122
6
118
16
200
263
110
139
281
122
7
118
16
200
110
263
139
281
122
8
118
16
200
110
139
263
281
122
9
118
16
200
110
139
263
281
122
10
118
16
200
110
139
263
122
281
11
118
16
200
110
139
263
122
281
12
118
16
200
110
139
263
122
281
13
16
118
200
110
139
263
122
281
14
16
118
200
110
139
263
122
281
15
16
118
110
200
139
263
122
281
16
16
118
110
139
200
263
122
281
17
16
118
110
139
200
263
122
281
18
16
118
110
139
200
122
263
281
19
16
118
110
139
200
122
263
281
20
16
118
110
139
200
122
263
281
21
16
118
110
139
200
122
263
281
22
16
110
118
139
200
122
263
281
23
16
110
118
139
200
122
263
281
24
16
110
118
139
200
122
263
281
25
16
110
118
139
122
200
263
281
26
16
110
118
139
122
200
263
281
27
16
110
118
139
122
200
263
281
28
16
110
118
139
122
200
263
281
29
16
110
118
139
122
200
263
281
30
16
110
118
139
122
200
263
281
31
16
110
118
122
139
200
263
281
32
16
110
118
122
139
200
263
281
33
16
110
118
122
139
200
263
281
34
16
110
118
122
139
200
263
281
35
16
110
118
122
139
200
263
281
36
16
110
118
122
139
200
263
281


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
248
277
264
87
132
93
258
238
2
248
277
264
87
132
93
258
238
3
248
277
264
87
132
93
258
238
4
93
277
264
87
132
248
258
238
5
93
277
264
87
132
248
258
238
6
93
132
264
87
277
248
258
238
7
93
132
264
87
277
248
258
238
8
93
132
87
264
277
248
258
238
9
93
132
87
264
277
248
258
238
10
93
132
87
264
277
248
258
238
11
93
87
132
264
277
248
258
238
12
93
87
132
264
277
248
258
238
13
93
87
132
264
277
248
258
238
14
87
93
132
264
277
248
258
238
15
87
93
132
264
277
248
258
238
16
87
93
132
264
277
248
258
238
17
87
93
132
238
277
248
258
264
18
87
93
132
238
277
248
258
264
19
87
93
132
238
248
277
258
264
20
87
93
132
238
248
277
258
264
21
87
93
132
238
248
277
258
264
22
87
93
132
238
248
277
258
264
23
87
93
132
238
248
277
258
264
24
87
93
132
238
248
277
258
264
25
87
93
132
238
248
258
277
264
26
87
93
132
238
248
258
277
264
27
87
93
132
238
248
258
277
264
28
87
93
132
238
248
258
264
277


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
107
268
79
241
121
279
247
286
2
107
268
79
241
121
279
247
286
3
107
268
79
286
121
279
247
241
4
107
268
79
286
121
279
247
241
5
107
268
279
286
121
79
247
241
6
107
268
279
286
121
79
247
241
7
107
286
279
268
121
79
247
241
8
107
286
279
268
121
79
247
241
9
286
107
279
268
121
79
247
241
10
286
107
279
268
121
79
247
241
11
286
279
107
268
121
79
247
241
12
286
279
107
268
121
79
247
241
13
286
279
121
268
107
79
247
241
14
286
279
121
268
107
79
247
241
15
241
279
121
268
107
79
247
286
16
241
279
121
268
107
79
247
286
17
279
241
121
268
107
79
247
286
18
279
241
121
268
107
79
247
286
19
279
268
121
241
107
79
247
286
20
279
268
121
241
107
79
247
286
21
279
268
121
247
107
79
241
286
22
279
268
121
247
107
79
241
286
23
241
268
121
247
107
79
279
286
24
241
268
121
247
107
79
279
286
25
268
241
121
247
107
79
279
286
26
268
241
121
247
107
79
279
286
27
268
247
121
241
107
79
279
286
28
268
247
121
241
107
79
279
286
29
79
247
121
241
107
268
279
286
30
79
247
121
241
107
268
279
286
31
247
79
121
241
107
268
279
286
32
247
79
121
241
107
268
279
286
33
247
241
121
79
107
268
279
286
34
247
241
121
79
107
268
279
286
35
107
241
121
79
247
268
279
286
36
107
241
121
79
247
268
279
286
37
241
107
121
79
247
268
279
286
38
241
107
121
79
247
268
279
286
39
241
121
107
79
247
268
279
286
40
241
121
107
79
247
268
279
286
41
79
121
107
241
247
268
279
286
42
79
121
107
241
247
268
279
286
43
121
79
107
241
247
268
279
286
44
121
79
107
241
247
268
279
286
45
121
107
79
241
247
268
279
286
46
121
107
79
241
247
268
279
286
47
79
107
121
241
247
268
279
286
48
79
107
121
241
247
268
279
286
49
107
79
121
241
247
268
279
286
50
107
79
121
241
247
268
279
286
51
79
107
121
241
247
268
279
286


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
260

119
129
148
177
260
266
347
2
260

119
129
148
177
260
266
347
3
260

119
129
148
177
260
266
347
4
260

119
129
148
177
260
266
347
5
260

119
129
148
177
260
266
347
6
260

119
129
148
177
260
266
347


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
69

7
33
69
86
174
244
254
265
295
300
306
308
317
2
69

7
33
69
86
174
244
254
265
295
300
306
308
317
3
69

7
33
69
86
174
244
254
265
295
300
306
308
317


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!