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
221
13
92
70
215
356
114
271
2
221
13
92
70
215
356
114
271
3
13
221
92
70
215
356
114
271
4
13
221
92
70
215
356
114
271
5
13
92
221
70
215
356
114
271
6
13
92
221
70
215
356
114
271
7
13
92
70
221
215
356
114
271
8
13
70
92
221
215
356
114
271
9
13
70
92
221
215
356
114
271
10
13
70
92
215
221
356
114
271
11
13
70
92
215
221
356
114
271
12
13
70
92
215
221
356
114
271
13
13
70
92
215
221
114
356
271
14
13
70
92
215
114
221
356
271
15
13
70
92
114
215
221
356
271
16
13
70
92
114
215
221
356
271
17
13
70
92
114
215
221
271
356
18
13
70
92
114
215
221
271
356


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
110
283
303
260
16
75
165
164
2
110
283
303
260
16
75
165
164
3
110
283
303
260
16
75
165
164
4
110
283
303
260
16
75
165
164
5
110
283
303
260
16
75
165
164
6
110
283
260
303
16
75
165
164
7
110
283
260
16
303
75
165
164
8
110
283
260
16
75
303
165
164
9
110
283
260
16
75
165
303
164
10
110
283
260
16
75
165
164
303
11
110
283
260
16
75
165
164
303
12
110
283
260
16
75
165
164
303
13
110
283
260
16
75
165
164
303
14
110
260
283
16
75
165
164
303
15
110
260
16
283
75
165
164
303
16
110
260
16
75
283
165
164
303
17
110
260
16
75
165
283
164
303
18
110
260
16
75
165
164
283
303
19
110
260
16
75
165
164
283
303
20
110
260
16
75
165
164
283
303
21
110
260
16
75
165
164
283
303
22
110
16
260
75
165
164
283
303
23
110
16
75
260
165
164
283
303
24
110
16
75
165
260
164
283
303
25
110
16
75
165
164
260
283
303
26
110
16
75
165
164
260
283
303
27
110
16
75
165
164
260
283
303
28
16
110
75
165
164
260
283
303
29
16
75
110
165
164
260
283
303
30
16
75
110
165
164
260
283
303
31
16
75
110
164
165
260
283
303
32
16
75
110
164
165
260
283
303
33
16
75
110
164
165
260
283
303
34
16
75
110
164
165
260
283
303
35
16
75
110
164
165
260
283
303
36
16
75
110
164
165
260
283
303


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
15
2
300
247
57
123
244
214
2
15
2
300
247
57
123
244
214
3
15
2
300
247
57
123
244
214
4
15
2
57
247
300
123
244
214
5
15
2
57
247
300
123
244
214
6
15
2
57
247
300
123
244
214
7
2
15
57
247
300
123
244
214
8
2
15
57
247
300
123
244
214
9
2
15
57
247
300
123
244
214
10
2
15
57
247
300
123
244
214
11
2
15
57
247
300
123
244
214
12
2
15
57
247
300
123
244
214
13
2
15
57
123
300
247
244
214
14
2
15
57
123
300
247
244
214
15
2
15
57
123
300
247
244
214
16
2
15
57
123
214
247
244
300
17
2
15
57
123
214
247
244
300
18
2
15
57
123
214
244
247
300
19
2
15
57
123
214
244
247
300
20
2
15
57
123
214
244
247
300
21
2
15
57
123
214
244
247
300
22
2
15
57
123
214
244
247
300
23
2
15
57
123
214
244
247
300
24
2
15
57
123
214
244
247
300


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


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
276

120
241
276
288
305
314
339
2
276

120
241
276
288
305
314
339
3
276

120
241
276
288
305
314
339
4
276

120
241
276
288
305
314
339


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
35

21
35
69
126
247
251
254
256
300
322
325
328
356
2
35

21
35
69
126
247
251
254
256
300
322
325
328
356
3
35

21
35
69
126
247
251
254
256
300
322
325
328
356
4
35

21
35
69
126
247
251
254
256
300
322
325
328
356
5
35

21
35
69
126
247
251
254
256
300
322
325
328
356


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!