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
343
112
6
179
201
133
129
244
2
343
112
6
179
201
133
129
244
3
112
343
6
179
201
133
129
244
4
112
343
6
179
201
133
129
244
5
112
6
343
179
201
133
129
244
6
6
112
343
179
201
133
129
244
7
6
112
343
179
201
133
129
244
8
6
112
179
343
201
133
129
244
9
6
112
179
343
201
133
129
244
10
6
112
179
201
343
133
129
244
11
6
112
179
201
343
133
129
244
12
6
112
179
201
133
343
129
244
13
6
112
179
133
201
343
129
244
14
6
112
133
179
201
343
129
244
15
6
112
133
179
201
343
129
244
16
6
112
133
179
201
129
343
244
17
6
112
133
179
129
201
343
244
18
6
112
133
129
179
201
343
244
19
6
112
129
133
179
201
343
244
20
6
112
129
133
179
201
343
244
21
6
112
129
133
179
201
244
343
22
6
112
129
133
179
201
244
343


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
126
183
14
308
195
235
68
357
2
126
183
14
308
195
235
68
357
3
126
183
14
308
195
235
68
357
4
126
183
14
308
195
235
68
357
5
126
14
183
308
195
235
68
357
6
126
14
183
308
195
235
68
357
7
126
14
183
195
308
235
68
357
8
126
14
183
195
235
308
68
357
9
126
14
183
195
235
68
308
357
10
126
14
183
195
235
68
308
357
11
126
14
183
195
235
68
308
357
12
126
14
183
195
235
68
308
357
13
14
126
183
195
235
68
308
357
14
14
126
183
195
235
68
308
357
15
14
126
183
195
235
68
308
357
16
14
126
183
195
235
68
308
357
17
14
126
183
195
68
235
308
357
18
14
126
183
195
68
235
308
357
19
14
126
183
195
68
235
308
357
20
14
126
183
195
68
235
308
357
21
14
126
183
195
68
235
308
357
22
14
126
183
195
68
235
308
357
23
14
126
183
195
68
235
308
357
24
14
126
183
68
195
235
308
357
25
14
126
183
68
195
235
308
357
26
14
126
183
68
195
235
308
357
27
14
126
183
68
195
235
308
357
28
14
126
183
68
195
235
308
357
29
14
126
183
68
195
235
308
357
30
14
126
68
183
195
235
308
357
31
14
126
68
183
195
235
308
357
32
14
126
68
183
195
235
308
357
33
14
126
68
183
195
235
308
357
34
14
126
68
183
195
235
308
357
35
14
68
126
183
195
235
308
357
36
14
68
126
183
195
235
308
357
37
14
68
126
183
195
235
308
357
38
14
68
126
183
195
235
308
357
39
14
68
126
183
195
235
308
357
40
14
68
126
183
195
235
308
357


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
356
149
248
133
128
201
290
189
2
356
149
248
133
128
201
290
189
3
356
149
248
133
128
201
290
189
4
128
149
248
133
356
201
290
189
5
128
149
248
133
356
201
290
189
6
128
149
248
133
356
201
290
189
7
128
149
248
133
189
201
290
356
8
128
149
248
133
189
201
290
356
9
128
149
248
133
189
201
290
356
10
128
149
189
133
248
201
290
356
11
128
149
189
133
248
201
290
356
12
128
149
189
133
248
201
290
356
13
128
149
133
189
248
201
290
356
14
128
149
133
189
248
201
290
356
15
128
149
133
189
248
201
290
356
16
128
133
149
189
248
201
290
356
17
128
133
149
189
248
201
290
356
18
128
133
149
189
248
201
290
356
19
128
133
149
189
201
248
290
356
20
128
133
149
189
201
248
290
356
21
128
133
149
189
201
248
290
356
22
128
133
149
189
201
248
290
356


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
55
309
274
71
218
328
47
299
2
55
309
274
71
218
328
47
299
3
55
309
274
299
218
328
47
71
4
55
309
274
299
218
328
47
71
5
55
309
328
299
218
274
47
71
6
55
309
328
299
218
274
47
71
7
55
328
309
299
218
274
47
71
8
55
328
309
299
218
274
47
71
9
328
55
309
299
218
274
47
71
10
328
55
309
299
218
274
47
71
11
328
309
55
299
218
274
47
71
12
328
309
55
299
218
274
47
71
13
328
309
274
299
218
55
47
71
14
328
309
274
299
218
55
47
71
15
71
309
274
299
218
55
47
328
16
71
309
274
299
218
55
47
328
17
309
71
274
299
218
55
47
328
18
309
71
274
299
218
55
47
328
19
309
299
274
71
218
55
47
328
20
309
299
274
71
218
55
47
328
21
47
299
274
71
218
55
309
328
22
47
299
274
71
218
55
309
328
23
299
47
274
71
218
55
309
328
24
299
47
274
71
218
55
309
328
25
299
274
47
71
218
55
309
328
26
299
274
47
71
218
55
309
328
27
299
274
218
71
47
55
309
328
28
299
274
218
71
47
55
309
328
29
55
274
218
71
47
299
309
328
30
55
274
218
71
47
299
309
328
31
274
55
218
71
47
299
309
328
32
274
55
218
71
47
299
309
328
33
274
218
55
71
47
299
309
328
34
274
218
55
71
47
299
309
328
35
47
218
55
71
274
299
309
328
36
47
218
55
71
274
299
309
328
37
218
47
55
71
274
299
309
328
38
218
47
55
71
274
299
309
328
39
218
71
55
47
274
299
309
328
40
218
71
55
47
274
299
309
328
41
47
71
55
218
274
299
309
328
42
47
71
55
218
274
299
309
328
43
71
47
55
218
274
299
309
328
44
71
47
55
218
274
299
309
328
45
71
55
47
218
274
299
309
328
46
71
55
47
218
274
299
309
328
47
47
55
71
218
274
299
309
328
48
47
55
71
218
274
299
309
328
49
55
47
71
218
274
299
309
328
50
55
47
71
218
274
299
309
328
51
47
55
71
218
274
299
309
328


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
58

56
58
141
188
230
275
305
2
58

56
58
141
188
230
275
305
3
58

56
58
141
188
230
275
305


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
20

20
127
176
212
214
240
278
291
304
317
330
330
331
2
20

20
127
176
212
214
240
278
291
304
317
330
330
331
3
20

20
127
176
212
214
240
278
291
304
317
330
330
331
4
20

20
127
176
212
214
240
278
291
304
317
330
330
331


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!