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
185
192
46
160
173
123
57
152
2
185
192
46
160
173
123
57
152
3
185
192
46
160
173
123
57
152
4
185
46
192
160
173
123
57
152
5
46
185
192
160
173
123
57
152
6
46
185
192
160
173
123
57
152
7
46
185
160
192
173
123
57
152
8
46
160
185
192
173
123
57
152
9
46
160
185
192
173
123
57
152
10
46
160
185
173
192
123
57
152
11
46
160
173
185
192
123
57
152
12
46
160
173
185
192
123
57
152
13
46
160
173
185
123
192
57
152
14
46
160
173
123
185
192
57
152
15
46
160
123
173
185
192
57
152
16
46
123
160
173
185
192
57
152
17
46
123
160
173
185
192
57
152
18
46
123
160
173
185
57
192
152
19
46
123
160
173
57
185
192
152
20
46
123
160
57
173
185
192
152
21
46
123
57
160
173
185
192
152
22
46
57
123
160
173
185
192
152
23
46
57
123
160
173
185
192
152
24
46
57
123
160
173
185
152
192
25
46
57
123
160
173
152
185
192
26
46
57
123
160
152
173
185
192
27
46
57
123
152
160
173
185
192
28
46
57
123
152
160
173
185
192


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
23
339
24
95
228
32
215
143
2
23
339
24
95
228
32
215
143
3
23
339
24
95
228
32
215
143
4
23
339
24
95
228
32
215
143
5
23
24
339
95
228
32
215
143
6
23
24
95
339
228
32
215
143
7
23
24
95
228
339
32
215
143
8
23
24
95
228
32
339
215
143
9
23
24
95
228
32
215
339
143
10
23
24
95
228
32
215
143
339
11
23
24
95
228
32
215
143
339
12
23
24
95
228
32
215
143
339
13
23
24
95
228
32
215
143
339
14
23
24
95
228
32
215
143
339
15
23
24
95
228
32
215
143
339
16
23
24
95
32
228
215
143
339
17
23
24
95
32
215
228
143
339
18
23
24
95
32
215
143
228
339
19
23
24
95
32
215
143
228
339
20
23
24
95
32
215
143
228
339
21
23
24
95
32
215
143
228
339
22
23
24
95
32
215
143
228
339
23
23
24
32
95
215
143
228
339
24
23
24
32
95
215
143
228
339
25
23
24
32
95
143
215
228
339
26
23
24
32
95
143
215
228
339
27
23
24
32
95
143
215
228
339
28
23
24
32
95
143
215
228
339
29
23
24
32
95
143
215
228
339
30
23
24
32
95
143
215
228
339
31
23
24
32
95
143
215
228
339


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
156
127
245
163
12
247
316
32
2
156
127
245
163
12
247
316
32
3
156
127
245
163
12
247
316
32
4
12
127
245
163
156
247
316
32
5
12
127
245
163
156
247
316
32
6
12
127
245
163
156
247
316
32
7
12
127
32
163
156
247
316
245
8
12
127
32
163
156
247
316
245
9
12
127
32
156
163
247
316
245
10
12
127
32
156
163
247
316
245
11
12
127
32
156
163
247
316
245
12
12
32
127
156
163
247
316
245
13
12
32
127
156
163
247
316
245
14
12
32
127
156
163
247
316
245
15
12
32
127
156
163
247
316
245
16
12
32
127
156
163
247
316
245
17
12
32
127
156
163
247
316
245
18
12
32
127
156
163
247
245
316
19
12
32
127
156
163
247
245
316
20
12
32
127
156
163
247
245
316
21
12
32
127
156
163
245
247
316
22
12
32
127
156
163
245
247
316
23
12
32
127
156
163
245
247
316
24
12
32
127
156
163
245
247
316


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


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
312

67
77
94
94
105
312
359
2
312

67
77
94
94
105
312
359
3
312

67
77
94
94
105
312
359
4
312

67
77
94
94
105
312
359
5
312

67
77
94
94
105
312
359
6
312

67
77
94
94
105
312
359
7
312

67
77
94
94
105
312
359


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
80

46
47
50
80
81
101
148
148
190
245
264
275
293
2
80

46
47
50
80
81
101
148
148
190
245
264
275
293
3
80

46
47
50
80
81
101
148
148
190
245
264
275
293
4
80

46
47
50
80
81
101
148
148
190
245
264
275
293
5
80

46
47
50
80
81
101
148
148
190
245
264
275
293


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!