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
156
73
98
154
12
310
23
95
2
156
73
98
154
12
310
23
95
3
73
156
98
154
12
310
23
95
4
73
156
98
154
12
310
23
95
5
73
98
156
154
12
310
23
95
6
73
98
156
154
12
310
23
95
7
73
98
154
156
12
310
23
95
8
73
98
154
156
12
310
23
95
9
73
98
154
12
156
310
23
95
10
73
98
12
154
156
310
23
95
11
73
12
98
154
156
310
23
95
12
12
73
98
154
156
310
23
95
13
12
73
98
154
156
310
23
95
14
12
73
98
154
156
310
23
95
15
12
73
98
154
156
23
310
95
16
12
73
98
154
23
156
310
95
17
12
73
98
23
154
156
310
95
18
12
73
23
98
154
156
310
95
19
12
23
73
98
154
156
310
95
20
12
23
73
98
154
156
310
95
21
12
23
73
98
154
156
95
310
22
12
23
73
98
154
95
156
310
23
12
23
73
98
95
154
156
310
24
12
23
73
95
98
154
156
310
25
12
23
73
95
98
154
156
310


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


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
185
136
8
5
194
22
245
330
2
185
136
8
5
194
22
245
330
3
185
136
8
5
194
22
245
330
4
185
136
8
5
22
194
245
330
5
185
136
8
5
22
194
245
330
6
185
136
8
5
22
194
245
330
7
5
136
8
185
22
194
245
330
8
5
136
8
185
22
194
245
330
9
5
8
136
185
22
194
245
330
10
5
8
136
185
22
194
245
330
11
5
8
136
185
22
194
245
330
12
5
8
136
185
22
194
245
330
13
5
8
136
185
22
194
245
330
14
5
8
136
185
22
194
245
330
15
5
8
136
22
185
194
245
330
16
5
8
136
22
185
194
245
330
17
5
8
136
22
185
194
245
330
18
5
8
22
136
185
194
245
330
19
5
8
22
136
185
194
245
330
20
5
8
22
136
185
194
245
330
21
5
8
22
136
185
194
245
330


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
258
75
106
98
78
126
232
202
2
258
75
106
98
78
126
232
202
3
258
75
106
232
78
126
98
202
4
258
75
106
232
78
126
98
202
5
258
75
126
232
78
106
98
202
6
258
75
126
232
78
106
98
202
7
258
232
126
75
78
106
98
202
8
258
232
126
75
78
106
98
202
9
258
232
126
202
78
106
98
75
10
258
232
126
202
78
106
98
75
11
75
232
126
202
78
106
98
258
12
75
232
126
202
78
106
98
258
13
232
75
126
202
78
106
98
258
14
232
75
126
202
78
106
98
258
15
232
202
126
75
78
106
98
258
16
232
202
126
75
78
106
98
258
17
232
202
126
98
78
106
75
258
18
232
202
126
98
78
106
75
258
19
75
202
126
98
78
106
232
258
20
75
202
126
98
78
106
232
258
21
202
75
126
98
78
106
232
258
22
202
75
126
98
78
106
232
258
23
202
126
75
98
78
106
232
258
24
202
126
75
98
78
106
232
258
25
202
126
106
98
78
75
232
258
26
202
126
106
98
78
75
232
258
27
75
126
106
98
78
202
232
258
28
75
126
106
98
78
202
232
258
29
126
75
106
98
78
202
232
258
30
126
75
106
98
78
202
232
258
31
126
106
75
98
78
202
232
258
32
126
106
75
98
78
202
232
258
33
126
106
78
98
75
202
232
258
34
126
106
78
98
75
202
232
258
35
75
106
78
98
126
202
232
258
36
75
106
78
98
126
202
232
258
37
106
75
78
98
126
202
232
258
38
106
75
78
98
126
202
232
258
39
106
98
78
75
126
202
232
258
40
106
98
78
75
126
202
232
258
41
75
98
78
106
126
202
232
258
42
75
98
78
106
126
202
232
258
43
98
75
78
106
126
202
232
258
44
98
75
78
106
126
202
232
258
45
98
78
75
106
126
202
232
258
46
98
78
75
106
126
202
232
258
47
75
78
98
106
126
202
232
258
48
75
78
98
106
126
202
232
258
49
78
75
98
106
126
202
232
258
50
78
75
98
106
126
202
232
258
51
75
78
98
106
126
202
232
258


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
202

118
202
210
260
283
317
345
2
202

118
202
210
260
283
317
345
3
202

118
202
210
260
283
317
345


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
98

39
56
89
98
99
117
129
181
182
233
260
298
298
2
98

39
56
89
98
99
117
129
181
182
233
260
298
298
3
98

39
56
89
98
99
117
129
181
182
233
260
298
298
4
98

39
56
89
98
99
117
129
181
182
233
260
298
298
5
98

39
56
89
98
99
117
129
181
182
233
260
298
298


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!