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
176
113
359
106
270
56
290
107
2
176
113
359
106
270
56
290
107
3
113
176
359
106
270
56
290
107
4
113
176
359
106
270
56
290
107
5
113
176
359
106
270
56
290
107
6
113
176
106
359
270
56
290
107
7
113
106
176
359
270
56
290
107
8
106
113
176
359
270
56
290
107
9
106
113
176
359
270
56
290
107
10
106
113
176
270
359
56
290
107
11
106
113
176
270
359
56
290
107
12
106
113
176
270
56
359
290
107
13
106
113
176
56
270
359
290
107
14
106
113
56
176
270
359
290
107
15
106
56
113
176
270
359
290
107
16
56
106
113
176
270
359
290
107
17
56
106
113
176
270
359
290
107
18
56
106
113
176
270
290
359
107
19
56
106
113
176
270
290
359
107
20
56
106
113
176
270
290
107
359
21
56
106
113
176
270
107
290
359
22
56
106
113
176
107
270
290
359
23
56
106
113
107
176
270
290
359
24
56
106
107
113
176
270
290
359
25
56
106
107
113
176
270
290
359


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
185
33
67
309
159
255
188
161
2
185
33
67
309
159
255
188
161
3
185
33
67
309
159
255
188
161
4
33
185
67
309
159
255
188
161
5
33
67
185
309
159
255
188
161
6
33
67
185
309
159
255
188
161
7
33
67
185
159
309
255
188
161
8
33
67
185
159
255
309
188
161
9
33
67
185
159
255
188
309
161
10
33
67
185
159
255
188
161
309
11
33
67
185
159
255
188
161
309
12
33
67
185
159
255
188
161
309
13
33
67
185
159
255
188
161
309
14
33
67
185
159
255
188
161
309
15
33
67
159
185
255
188
161
309
16
33
67
159
185
255
188
161
309
17
33
67
159
185
188
255
161
309
18
33
67
159
185
188
161
255
309
19
33
67
159
185
188
161
255
309
20
33
67
159
185
188
161
255
309
21
33
67
159
185
188
161
255
309
22
33
67
159
185
188
161
255
309
23
33
67
159
185
188
161
255
309
24
33
67
159
185
188
161
255
309
25
33
67
159
185
161
188
255
309
26
33
67
159
185
161
188
255
309
27
33
67
159
185
161
188
255
309
28
33
67
159
185
161
188
255
309
29
33
67
159
185
161
188
255
309
30
33
67
159
185
161
188
255
309
31
33
67
159
161
185
188
255
309
32
33
67
159
161
185
188
255
309
33
33
67
159
161
185
188
255
309
34
33
67
159
161
185
188
255
309
35
33
67
159
161
185
188
255
309
36
33
67
159
161
185
188
255
309


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
340
63
100
190
124
177
224
64
2
340
63
100
190
124
177
224
64
3
340
63
100
190
124
177
224
64
4
64
63
100
190
124
177
224
340
5
64
63
100
190
124
177
224
340
6
64
63
100
124
190
177
224
340
7
64
63
100
124
190
177
224
340
8
64
63
100
124
190
177
224
340
9
64
63
100
124
190
177
224
340
10
64
63
100
124
190
177
224
340
11
64
63
100
124
190
177
224
340
12
63
64
100
124
190
177
224
340
13
63
64
100
124
190
177
224
340
14
63
64
100
124
190
177
224
340
15
63
64
100
124
190
177
224
340
16
63
64
100
124
190
177
224
340
17
63
64
100
124
190
177
224
340
18
63
64
100
124
177
190
224
340


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
223
36
234
320
232
106
360
19
2
223
36
234
320
232
106
360
19
3
223
36
234
360
232
106
320
19
4
223
36
234
360
232
106
320
19
5
223
360
234
36
232
106
320
19
6
223
360
234
36
232
106
320
19
7
223
360
234
320
232
106
36
19
8
223
360
234
320
232
106
36
19
9
360
223
234
320
232
106
36
19
10
360
223
234
320
232
106
36
19
11
360
320
234
223
232
106
36
19
12
360
320
234
223
232
106
36
19
13
19
320
234
223
232
106
36
360
14
19
320
234
223
232
106
36
360
15
320
19
234
223
232
106
36
360
16
320
19
234
223
232
106
36
360
17
320
234
19
223
232
106
36
360
18
320
234
19
223
232
106
36
360
19
320
234
232
223
19
106
36
360
20
320
234
232
223
19
106
36
360
21
36
234
232
223
19
106
320
360
22
36
234
232
223
19
106
320
360
23
234
36
232
223
19
106
320
360
24
234
36
232
223
19
106
320
360
25
234
232
36
223
19
106
320
360
26
234
232
36
223
19
106
320
360
27
234
232
106
223
19
36
320
360
28
234
232
106
223
19
36
320
360
29
36
232
106
223
19
234
320
360
30
36
232
106
223
19
234
320
360
31
232
36
106
223
19
234
320
360
32
232
36
106
223
19
234
320
360
33
232
223
106
36
19
234
320
360
34
232
223
106
36
19
234
320
360
35
19
223
106
36
232
234
320
360
36
19
223
106
36
232
234
320
360
37
223
19
106
36
232
234
320
360
38
223
19
106
36
232
234
320
360
39
223
106
19
36
232
234
320
360
40
223
106
19
36
232
234
320
360
41
36
106
19
223
232
234
320
360
42
36
106
19
223
232
234
320
360
43
106
36
19
223
232
234
320
360
44
106
36
19
223
232
234
320
360
45
19
36
106
223
232
234
320
360
46
19
36
106
223
232
234
320
360
47
36
19
106
223
232
234
320
360
48
36
19
106
223
232
234
320
360
49
19
36
106
223
232
234
320
360


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
332

129
143
200
233
243
332
343
2
332

129
143
200
233
243
332
343
3
332

129
143
200
233
243
332
343
4
332

129
143
200
233
243
332
343
5
332

129
143
200
233
243
332
343
6
332

129
143
200
233
243
332
343
7
332

129
143
200
233
243
332
343


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
198

6
7
69
92
150
164
198
199
239
245
307
316
332
2
198

6
7
69
92
150
164
198
199
239
245
307
316
332


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!