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
277
312
158
125
63
203
279
21
2
277
312
158
125
63
203
279
21
3
277
312
158
125
63
203
279
21
4
277
158
312
125
63
203
279
21
5
158
277
312
125
63
203
279
21
6
158
277
312
125
63
203
279
21
7
158
277
125
312
63
203
279
21
8
158
125
277
312
63
203
279
21
9
125
158
277
312
63
203
279
21
10
125
158
277
312
63
203
279
21
11
125
158
277
63
312
203
279
21
12
125
158
63
277
312
203
279
21
13
125
63
158
277
312
203
279
21
14
63
125
158
277
312
203
279
21
15
63
125
158
277
312
203
279
21
16
63
125
158
277
203
312
279
21
17
63
125
158
203
277
312
279
21
18
63
125
158
203
277
312
279
21
19
63
125
158
203
277
279
312
21
20
63
125
158
203
277
279
312
21
21
63
125
158
203
277
279
21
312
22
63
125
158
203
277
21
279
312
23
63
125
158
203
21
277
279
312
24
63
125
158
21
203
277
279
312
25
63
125
21
158
203
277
279
312
26
63
21
125
158
203
277
279
312
27
21
63
125
158
203
277
279
312
28
21
63
125
158
203
277
279
312


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
83
188
123
102
114
24
73
302
2
83
188
123
102
114
24
73
302
3
83
188
123
102
114
24
73
302
4
83
188
123
102
114
24
73
302
5
83
123
188
102
114
24
73
302
6
83
123
102
188
114
24
73
302
7
83
123
102
114
188
24
73
302
8
83
123
102
114
24
188
73
302
9
83
123
102
114
24
73
188
302
10
83
123
102
114
24
73
188
302
11
83
123
102
114
24
73
188
302
12
83
123
102
114
24
73
188
302
13
83
123
102
114
24
73
188
302
14
83
102
123
114
24
73
188
302
15
83
102
114
123
24
73
188
302
16
83
102
114
24
123
73
188
302
17
83
102
114
24
73
123
188
302
18
83
102
114
24
73
123
188
302
19
83
102
114
24
73
123
188
302
20
83
102
114
24
73
123
188
302
21
83
102
114
24
73
123
188
302
22
83
102
114
24
73
123
188
302
23
83
102
24
114
73
123
188
302
24
83
102
24
73
114
123
188
302
25
83
102
24
73
114
123
188
302
26
83
102
24
73
114
123
188
302
27
83
102
24
73
114
123
188
302
28
83
102
24
73
114
123
188
302
29
83
24
102
73
114
123
188
302
30
83
24
73
102
114
123
188
302
31
83
24
73
102
114
123
188
302
32
83
24
73
102
114
123
188
302
33
83
24
73
102
114
123
188
302
34
24
83
73
102
114
123
188
302
35
24
73
83
102
114
123
188
302
36
24
73
83
102
114
123
188
302
37
24
73
83
102
114
123
188
302
38
24
73
83
102
114
123
188
302
39
24
73
83
102
114
123
188
302
40
24
73
83
102
114
123
188
302


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
90
86
41
141
269
215
258
91
2
90
86
41
141
269
215
258
91
3
90
86
41
141
269
215
258
91
4
90
86
41
141
91
215
258
269
5
90
86
41
141
91
215
258
269
6
90
86
41
141
91
215
258
269
7
90
86
41
91
141
215
258
269
8
90
86
41
91
141
215
258
269
9
90
86
41
91
141
215
258
269
10
41
86
90
91
141
215
258
269
11
41
86
90
91
141
215
258
269
12
41
86
90
91
141
215
258
269
13
41
86
90
91
141
215
258
269
14
41
86
90
91
141
215
258
269
15
41
86
90
91
141
215
258
269
16
41
86
90
91
141
215
258
269


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


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
271

78
150
197
233
260
270
271
2
271

78
150
197
233
260
270
271
3
271

78
150
197
233
260
270
271
4
271

78
150
197
233
260
270
271
5
271

78
150
197
233
260
270
271
6
271

78
150
197
233
260
270
271
7
271

78
150
197
233
260
270
271
8
271

78
150
197
233
260
270
271


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
39

22
35
39
80
107
117
124
135
152
172
290
296
314
2
39

22
35
39
80
107
117
124
135
152
172
290
296
314
3
39

22
35
39
80
107
117
124
135
152
172
290
296
314


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!