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
7
207
145
281
186
331
181
215
2
7
207
145
281
186
331
181
215
3
7
207
145
281
186
331
181
215
4
7
145
207
281
186
331
181
215
5
7
145
207
281
186
331
181
215
6
7
145
207
281
186
331
181
215
7
7
145
207
186
281
331
181
215
8
7
145
186
207
281
331
181
215
9
7
145
186
207
281
331
181
215
10
7
145
186
207
281
331
181
215
11
7
145
186
207
281
181
331
215
12
7
145
186
207
181
281
331
215
13
7
145
186
181
207
281
331
215
14
7
145
181
186
207
281
331
215
15
7
145
181
186
207
281
331
215
16
7
145
181
186
207
281
215
331
17
7
145
181
186
207
215
281
331
18
7
145
181
186
207
215
281
331


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
81
28
303
144
49
331
118
39
2
81
28
303
144
49
331
118
39
3
81
28
303
144
49
331
118
39
4
28
81
303
144
49
331
118
39
5
28
81
303
144
49
331
118
39
6
28
81
144
303
49
331
118
39
7
28
81
144
49
303
331
118
39
8
28
81
144
49
303
331
118
39
9
28
81
144
49
303
118
331
39
10
28
81
144
49
303
118
39
331
11
28
81
144
49
303
118
39
331
12
28
81
144
49
303
118
39
331
13
28
81
144
49
303
118
39
331
14
28
81
144
49
303
118
39
331
15
28
81
49
144
303
118
39
331
16
28
81
49
144
303
118
39
331
17
28
81
49
144
118
303
39
331
18
28
81
49
144
118
39
303
331
19
28
81
49
144
118
39
303
331
20
28
81
49
144
118
39
303
331
21
28
81
49
144
118
39
303
331
22
28
49
81
144
118
39
303
331
23
28
49
81
144
118
39
303
331
24
28
49
81
118
144
39
303
331
25
28
49
81
118
39
144
303
331
26
28
49
81
118
39
144
303
331
27
28
49
81
118
39
144
303
331
28
28
49
81
118
39
144
303
331
29
28
49
81
118
39
144
303
331
30
28
49
81
118
39
144
303
331
31
28
49
81
39
118
144
303
331
32
28
49
81
39
118
144
303
331
33
28
49
81
39
118
144
303
331
34
28
49
81
39
118
144
303
331
35
28
49
81
39
118
144
303
331
36
28
49
39
81
118
144
303
331
37
28
49
39
81
118
144
303
331
38
28
49
39
81
118
144
303
331
39
28
49
39
81
118
144
303
331
40
28
39
49
81
118
144
303
331
41
28
39
49
81
118
144
303
331
42
28
39
49
81
118
144
303
331
43
28
39
49
81
118
144
303
331


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
72
21
3
252
145
99
153
139
2
72
21
3
252
145
99
153
139
3
72
21
3
252
145
99
153
139
4
72
21
3
139
145
99
153
252
5
72
21
3
139
145
99
153
252
6
72
21
3
139
99
145
153
252
7
72
21
3
139
99
145
153
252
8
72
21
3
139
99
145
153
252
9
3
21
72
139
99
145
153
252
10
3
21
72
139
99
145
153
252
11
3
21
72
139
99
145
153
252
12
3
21
72
99
139
145
153
252
13
3
21
72
99
139
145
153
252
14
3
21
72
99
139
145
153
252
15
3
21
72
99
139
145
153
252
16
3
21
72
99
139
145
153
252
17
3
21
72
99
139
145
153
252
18
3
21
72
99
139
145
153
252


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
317
165
7
334
279
119
288
221
2
317
165
7
334
279
119
288
221
3
317
165
279
334
7
119
288
221
4
317
165
279
334
7
119
288
221
5
317
334
279
165
7
119
288
221
6
317
334
279
165
7
119
288
221
7
317
334
279
288
7
119
165
221
8
317
334
279
288
7
119
165
221
9
334
317
279
288
7
119
165
221
10
334
317
279
288
7
119
165
221
11
221
317
279
288
7
119
165
334
12
221
317
279
288
7
119
165
334
13
317
221
279
288
7
119
165
334
14
317
221
279
288
7
119
165
334
15
317
288
279
221
7
119
165
334
16
317
288
279
221
7
119
165
334
17
165
288
279
221
7
119
317
334
18
165
288
279
221
7
119
317
334
19
288
165
279
221
7
119
317
334
20
288
165
279
221
7
119
317
334
21
288
279
165
221
7
119
317
334
22
288
279
165
221
7
119
317
334
23
119
279
165
221
7
288
317
334
24
119
279
165
221
7
288
317
334
25
279
119
165
221
7
288
317
334
26
279
119
165
221
7
288
317
334
27
279
221
165
119
7
288
317
334
28
279
221
165
119
7
288
317
334
29
7
221
165
119
279
288
317
334
30
7
221
165
119
279
288
317
334
31
221
7
165
119
279
288
317
334
32
221
7
165
119
279
288
317
334
33
221
165
7
119
279
288
317
334
34
221
165
7
119
279
288
317
334
35
119
165
7
221
279
288
317
334
36
119
165
7
221
279
288
317
334
37
165
119
7
221
279
288
317
334
38
165
119
7
221
279
288
317
334
39
7
119
165
221
279
288
317
334
40
7
119
165
221
279
288
317
334
41
119
7
165
221
279
288
317
334
42
119
7
165
221
279
288
317
334
43
7
119
165
221
279
288
317
334


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
165

16
165
168
222
249
281
291
2
165

16
165
168
222
249
281
291
3
165

16
165
168
222
249
281
291


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
15

4
15
16
33
48
183
220
233
258
260
291
311
333
2
15

4
15
16
33
48
183
220
233
258
260
291
311
333
3
15

4
15
16
33
48
183
220
233
258
260
291
311
333
4
15

4
15
16
33
48
183
220
233
258
260
291
311
333
5
15

4
15
16
33
48
183
220
233
258
260
291
311
333


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!