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
333
119
208
131
77
329
118
194
2
333
119
208
131
77
329
118
194
3
119
333
208
131
77
329
118
194
4
119
333
208
131
77
329
118
194
5
119
208
333
131
77
329
118
194
6
119
208
333
131
77
329
118
194
7
119
208
131
333
77
329
118
194
8
119
131
208
333
77
329
118
194
9
119
131
208
333
77
329
118
194
10
119
131
208
77
333
329
118
194
11
119
131
77
208
333
329
118
194
12
119
77
131
208
333
329
118
194
13
77
119
131
208
333
329
118
194
14
77
119
131
208
333
329
118
194
15
77
119
131
208
329
333
118
194
16
77
119
131
208
329
333
118
194
17
77
119
131
208
329
118
333
194
18
77
119
131
208
118
329
333
194
19
77
119
131
118
208
329
333
194
20
77
119
118
131
208
329
333
194
21
77
118
119
131
208
329
333
194
22
77
118
119
131
208
329
333
194
23
77
118
119
131
208
329
194
333
24
77
118
119
131
208
194
329
333
25
77
118
119
131
194
208
329
333
26
77
118
119
131
194
208
329
333


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
198
94
283
276
175
253
243
28
2
198
94
283
276
175
253
243
28
3
198
94
283
276
175
253
243
28
4
94
198
283
276
175
253
243
28
5
94
198
283
276
175
253
243
28
6
94
198
276
283
175
253
243
28
7
94
198
276
175
283
253
243
28
8
94
198
276
175
253
283
243
28
9
94
198
276
175
253
243
283
28
10
94
198
276
175
253
243
28
283
11
94
198
276
175
253
243
28
283
12
94
198
276
175
253
243
28
283
13
94
198
276
175
253
243
28
283
14
94
198
276
175
253
243
28
283
15
94
198
175
276
253
243
28
283
16
94
198
175
253
276
243
28
283
17
94
198
175
253
243
276
28
283
18
94
198
175
253
243
28
276
283
19
94
198
175
253
243
28
276
283
20
94
198
175
253
243
28
276
283
21
94
198
175
253
243
28
276
283
22
94
175
198
253
243
28
276
283
23
94
175
198
253
243
28
276
283
24
94
175
198
243
253
28
276
283
25
94
175
198
243
28
253
276
283
26
94
175
198
243
28
253
276
283
27
94
175
198
243
28
253
276
283
28
94
175
198
243
28
253
276
283
29
94
175
198
243
28
253
276
283
30
94
175
198
243
28
253
276
283
31
94
175
198
28
243
253
276
283
32
94
175
198
28
243
253
276
283
33
94
175
198
28
243
253
276
283
34
94
175
198
28
243
253
276
283
35
94
175
198
28
243
253
276
283
36
94
175
28
198
243
253
276
283
37
94
175
28
198
243
253
276
283
38
94
175
28
198
243
253
276
283
39
94
175
28
198
243
253
276
283
40
94
28
175
198
243
253
276
283
41
94
28
175
198
243
253
276
283
42
94
28
175
198
243
253
276
283
43
28
94
175
198
243
253
276
283
44
28
94
175
198
243
253
276
283
45
28
94
175
198
243
253
276
283


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
179
65
154
143
65
263
125
14
2
179
65
154
143
65
263
125
14
3
179
65
154
143
65
263
125
14
4
14
65
154
143
65
263
125
179
5
14
65
154
143
65
263
125
179
6
14
65
154
143
65
263
125
179
7
14
65
154
143
65
263
125
179
8
14
65
154
143
65
263
125
179
9
14
65
154
143
65
263
125
179
10
14
65
154
143
65
263
125
179
11
14
65
154
143
65
263
125
179
12
14
65
154
143
65
179
125
263
13
14
65
154
143
65
179
125
263
14
14
65
154
143
65
179
125
263
15
14
65
65
143
154
179
125
263
16
14
65
65
143
154
179
125
263
17
14
65
65
143
154
179
125
263
18
14
65
65
143
154
125
179
263
19
14
65
65
143
154
125
179
263
20
14
65
65
143
154
125
179
263
21
14
65
65
143
125
154
179
263
22
14
65
65
143
125
154
179
263
23
14
65
65
143
125
154
179
263
24
14
65
65
125
143
154
179
263


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
268
340
124
92
1
231
193
188
2
268
340
124
92
1
231
193
188
3
268
340
124
193
1
231
92
188
4
268
340
124
193
1
231
92
188
5
268
340
231
193
1
124
92
188
6
268
340
231
193
1
124
92
188
7
340
268
231
193
1
124
92
188
8
340
268
231
193
1
124
92
188
9
188
268
231
193
1
124
92
340
10
188
268
231
193
1
124
92
340
11
268
188
231
193
1
124
92
340
12
268
188
231
193
1
124
92
340
13
268
231
188
193
1
124
92
340
14
268
231
188
193
1
124
92
340
15
92
231
188
193
1
124
268
340
16
92
231
188
193
1
124
268
340
17
231
92
188
193
1
124
268
340
18
231
92
188
193
1
124
268
340
19
231
193
188
92
1
124
268
340
20
231
193
188
92
1
124
268
340
21
124
193
188
92
1
231
268
340
22
124
193
188
92
1
231
268
340
23
193
124
188
92
1
231
268
340
24
193
124
188
92
1
231
268
340
25
193
188
124
92
1
231
268
340
26
193
188
124
92
1
231
268
340
27
1
188
124
92
193
231
268
340
28
1
188
124
92
193
231
268
340
29
188
1
124
92
193
231
268
340
30
188
1
124
92
193
231
268
340
31
188
124
1
92
193
231
268
340
32
188
124
1
92
193
231
268
340
33
92
124
1
188
193
231
268
340
34
92
124
1
188
193
231
268
340
35
124
92
1
188
193
231
268
340
36
124
92
1
188
193
231
268
340
37
1
92
124
188
193
231
268
340
38
1
92
124
188
193
231
268
340
39
92
1
124
188
193
231
268
340
40
92
1
124
188
193
231
268
340
41
1
92
124
188
193
231
268
340


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
350

27
31
72
78
224
340
350
2
350

27
31
72
78
224
340
350
3
350

27
31
72
78
224
340
350
4
350

27
31
72
78
224
340
350
5
350

27
31
72
78
224
340
350
6
350

27
31
72
78
224
340
350
7
350

27
31
72
78
224
340
350
8
350

27
31
72
78
224
340
350


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
252

113
120
172
180
187
203
238
247
252
253
255
342
355
2
252

113
120
172
180
187
203
238
247
252
253
255
342
355
3
252

113
120
172
180
187
203
238
247
252
253
255
342
355
4
252

113
120
172
180
187
203
238
247
252
253
255
342
355


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!