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
303
239
26
306
245
269
323
108
2
303
239
26
306
245
269
323
108
3
239
303
26
306
245
269
323
108
4
239
303
26
306
245
269
323
108
5
239
26
303
306
245
269
323
108
6
26
239
303
306
245
269
323
108
7
26
239
303
306
245
269
323
108
8
26
239
303
306
245
269
323
108
9
26
239
303
245
306
269
323
108
10
26
239
245
303
306
269
323
108
11
26
239
245
303
306
269
323
108
12
26
239
245
303
269
306
323
108
13
26
239
245
269
303
306
323
108
14
26
239
245
269
303
306
323
108
15
26
239
245
269
303
306
323
108
16
26
239
245
269
303
306
108
323
17
26
239
245
269
303
108
306
323
18
26
239
245
269
108
303
306
323
19
26
239
245
108
269
303
306
323
20
26
239
108
245
269
303
306
323
21
26
108
239
245
269
303
306
323
22
26
108
239
245
269
303
306
323


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
127
175
70
146
29
275
337
78
2
127
175
70
146
29
275
337
78
3
127
175
70
146
29
275
337
78
4
127
175
70
146
29
275
337
78
5
127
70
175
146
29
275
337
78
6
127
70
146
175
29
275
337
78
7
127
70
146
29
175
275
337
78
8
127
70
146
29
175
275
337
78
9
127
70
146
29
175
275
337
78
10
127
70
146
29
175
275
78
337
11
127
70
146
29
175
275
78
337
12
127
70
146
29
175
275
78
337
13
70
127
146
29
175
275
78
337
14
70
127
146
29
175
275
78
337
15
70
127
29
146
175
275
78
337
16
70
127
29
146
175
275
78
337
17
70
127
29
146
175
275
78
337
18
70
127
29
146
175
78
275
337
19
70
127
29
146
175
78
275
337
20
70
127
29
146
175
78
275
337
21
70
127
29
146
175
78
275
337
22
70
29
127
146
175
78
275
337
23
70
29
127
146
175
78
275
337
24
70
29
127
146
175
78
275
337
25
70
29
127
146
78
175
275
337
26
70
29
127
146
78
175
275
337
27
70
29
127
146
78
175
275
337
28
29
70
127
146
78
175
275
337
29
29
70
127
146
78
175
275
337
30
29
70
127
146
78
175
275
337
31
29
70
127
78
146
175
275
337
32
29
70
127
78
146
175
275
337
33
29
70
127
78
146
175
275
337
34
29
70
127
78
146
175
275
337
35
29
70
127
78
146
175
275
337
36
29
70
78
127
146
175
275
337
37
29
70
78
127
146
175
275
337
38
29
70
78
127
146
175
275
337
39
29
70
78
127
146
175
275
337
40
29
70
78
127
146
175
275
337


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
230
345
224
18
237
95
150
225
2
230
345
224
18
237
95
150
225
3
230
345
224
18
237
95
150
225
4
230
225
224
18
237
95
150
345
5
230
225
224
18
237
95
150
345
6
230
225
224
18
150
95
237
345
7
230
225
224
18
150
95
237
345
8
230
225
224
18
150
95
237
345
9
18
225
224
230
150
95
237
345
10
18
225
224
230
150
95
237
345
11
18
225
224
230
150
95
237
345
12
18
225
224
95
150
230
237
345
13
18
225
224
95
150
230
237
345
14
18
225
224
95
150
230
237
345
15
18
95
224
225
150
230
237
345
16
18
95
224
225
150
230
237
345
17
18
95
224
225
150
230
237
345
18
18
95
224
150
225
230
237
345
19
18
95
224
150
225
230
237
345
20
18
95
224
150
225
230
237
345
21
18
95
150
224
225
230
237
345
22
18
95
150
224
225
230
237
345
23
18
95
150
224
225
230
237
345
24
18
95
150
224
225
230
237
345


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


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
217

31
49
116
217
307
330
341
2
217

31
49
116
217
307
330
341
3
217

31
49
116
217
307
330
341
4
217

31
49
116
217
307
330
341
5
217

31
49
116
217
307
330
341


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
194

4
18
101
129
136
194
211
251
263
268
280
293
347
2
194

4
18
101
129
136
194
211
251
263
268
280
293
347
3
194

4
18
101
129
136
194
211
251
263
268
280
293
347
4
194

4
18
101
129
136
194
211
251
263
268
280
293
347
5
194

4
18
101
129
136
194
211
251
263
268
280
293
347


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!