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
151
196
56
359
218
359
11
2
176
151
196
56
359
218
359
11
3
151
176
196
56
359
218
359
11
4
151
176
196
56
359
218
359
11
5
151
176
196
56
359
218
359
11
6
151
176
56
196
359
218
359
11
7
151
56
176
196
359
218
359
11
8
56
151
176
196
359
218
359
11
9
56
151
176
196
359
218
359
11
10
56
151
176
196
359
218
359
11
11
56
151
176
196
218
359
359
11
12
56
151
176
196
218
359
359
11
13
56
151
176
196
218
359
359
11
14
56
151
176
196
218
359
11
359
15
56
151
176
196
218
11
359
359
16
56
151
176
196
11
218
359
359
17
56
151
176
11
196
218
359
359
18
56
151
11
176
196
218
359
359
19
56
11
151
176
196
218
359
359
20
11
56
151
176
196
218
359
359
21
11
56
151
176
196
218
359
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
207
184
8
4
52
352
331
24
2
207
184
8
4
52
352
331
24
3
207
184
8
4
52
352
331
24
4
184
207
8
4
52
352
331
24
5
184
8
207
4
52
352
331
24
6
184
8
4
207
52
352
331
24
7
184
8
4
52
207
352
331
24
8
184
8
4
52
207
352
331
24
9
184
8
4
52
207
331
352
24
10
184
8
4
52
207
331
24
352
11
184
8
4
52
207
331
24
352
12
184
8
4
52
207
331
24
352
13
8
184
4
52
207
331
24
352
14
8
4
184
52
207
331
24
352
15
8
4
52
184
207
331
24
352
16
8
4
52
184
207
331
24
352
17
8
4
52
184
207
331
24
352
18
8
4
52
184
207
24
331
352
19
8
4
52
184
207
24
331
352
20
8
4
52
184
207
24
331
352
21
4
8
52
184
207
24
331
352
22
4
8
52
184
207
24
331
352
23
4
8
52
184
207
24
331
352
24
4
8
52
184
207
24
331
352
25
4
8
52
184
24
207
331
352
26
4
8
52
184
24
207
331
352
27
4
8
52
184
24
207
331
352
28
4
8
52
184
24
207
331
352
29
4
8
52
184
24
207
331
352
30
4
8
52
184
24
207
331
352
31
4
8
52
24
184
207
331
352
32
4
8
52
24
184
207
331
352
33
4
8
52
24
184
207
331
352
34
4
8
52
24
184
207
331
352
35
4
8
52
24
184
207
331
352
36
4
8
24
52
184
207
331
352
37
4
8
24
52
184
207
331
352
38
4
8
24
52
184
207
331
352
39
4
8
24
52
184
207
331
352
40
4
8
24
52
184
207
331
352


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
10
238
220
243
179
60
36
291
2
10
238
220
243
179
60
36
291
3
10
238
220
243
179
60
36
291
4
10
36
220
243
179
60
238
291
5
10
36
220
243
179
60
238
291
6
10
36
60
243
179
220
238
291
7
10
36
60
243
179
220
238
291
8
10
36
60
179
243
220
238
291
9
10
36
60
179
243
220
238
291
10
10
36
60
179
243
220
238
291
11
10
36
60
179
243
220
238
291
12
10
36
60
179
243
220
238
291
13
10
36
60
179
243
220
238
291
14
10
36
60
179
243
220
238
291
15
10
36
60
179
243
220
238
291
16
10
36
60
179
243
220
238
291
17
10
36
60
179
238
220
243
291
18
10
36
60
179
238
220
243
291
19
10
36
60
179
238
220
243
291
20
10
36
60
179
220
238
243
291
21
10
36
60
179
220
238
243
291
22
10
36
60
179
220
238
243
291
23
10
36
60
179
220
238
243
291


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


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
266

18
48
69
126
166
266
307
2
266

18
48
69
126
166
266
307
3
266

18
48
69
126
166
266
307
4
266

18
48
69
126
166
266
307
5
266

18
48
69
126
166
266
307
6
266

18
48
69
126
166
266
307
7
266

18
48
69
126
166
266
307


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
50

50
77
99
114
120
122
133
150
167
178
290
337
352
2
50

50
77
99
114
120
122
133
150
167
178
290
337
352
3
50

50
77
99
114
120
122
133
150
167
178
290
337
352
4
50

50
77
99
114
120
122
133
150
167
178
290
337
352


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!