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
318
18
259
340
319
314
338
222
2
318
18
259
340
319
314
338
222
3
18
318
259
340
319
314
338
222
4
18
318
259
340
319
314
338
222
5
18
259
318
340
319
314
338
222
6
18
259
318
340
319
314
338
222
7
18
259
318
340
319
314
338
222
8
18
259
318
319
340
314
338
222
9
18
259
318
319
340
314
338
222
10
18
259
318
319
314
340
338
222
11
18
259
318
314
319
340
338
222
12
18
259
314
318
319
340
338
222
13
18
259
314
318
319
340
338
222
14
18
259
314
318
319
338
340
222
15
18
259
314
318
319
338
340
222
16
18
259
314
318
319
338
222
340
17
18
259
314
318
319
222
338
340
18
18
259
314
318
222
319
338
340
19
18
259
314
222
318
319
338
340
20
18
259
222
314
318
319
338
340
21
18
222
259
314
318
319
338
340
22
18
222
259
314
318
319
338
340


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


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
192
197
307
209
9
120
84
284
2
192
197
307
209
9
120
84
284
3
192
197
307
209
9
120
84
284
4
9
197
307
209
192
120
84
284
5
9
197
307
209
192
120
84
284
6
9
197
307
209
192
120
84
284
7
9
84
307
209
192
120
197
284
8
9
84
307
209
192
120
197
284
9
9
84
120
209
192
307
197
284
10
9
84
120
209
192
307
197
284
11
9
84
120
192
209
307
197
284
12
9
84
120
192
209
307
197
284
13
9
84
120
192
209
307
197
284
14
9
84
120
192
209
307
197
284
15
9
84
120
192
209
307
197
284
16
9
84
120
192
209
307
197
284
17
9
84
120
192
197
307
209
284
18
9
84
120
192
197
307
209
284
19
9
84
120
192
197
307
209
284
20
9
84
120
192
197
209
307
284
21
9
84
120
192
197
209
307
284
22
9
84
120
192
197
209
307
284
23
9
84
120
192
197
209
284
307


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


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
191

24
81
190
191
234
316
343
2
191

24
81
190
191
234
316
343
3
191

24
81
190
191
234
316
343
4
191

24
81
190
191
234
316
343
5
191

24
81
190
191
234
316
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
360

42
58
93
135
141
165
216
301
325
332
333
348
360
2
360

42
58
93
135
141
165
216
301
325
332
333
348
360
3
360

42
58
93
135
141
165
216
301
325
332
333
348
360
4
360

42
58
93
135
141
165
216
301
325
332
333
348
360


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!