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
76
10
49
93
162
125
149
164
2
76
10
49
93
162
125
149
164
3
10
76
49
93
162
125
149
164
4
10
76
49
93
162
125
149
164
5
10
49
76
93
162
125
149
164
6
10
49
76
93
162
125
149
164
7
10
49
76
93
162
125
149
164
8
10
49
76
93
162
125
149
164
9
10
49
76
93
125
162
149
164
10
10
49
76
93
125
162
149
164
11
10
49
76
93
125
149
162
164
12
10
49
76
93
125
149
162
164
13
10
49
76
93
125
149
162
164


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
242
97
232
137
112
129
254
218
2
242
97
232
137
112
129
254
218
3
242
97
232
137
112
129
254
218
4
97
242
232
137
112
129
254
218
5
97
232
242
137
112
129
254
218
6
97
232
137
242
112
129
254
218
7
97
232
137
112
242
129
254
218
8
97
232
137
112
129
242
254
218
9
97
232
137
112
129
242
254
218
10
97
232
137
112
129
242
218
254
11
97
232
137
112
129
242
218
254
12
97
232
137
112
129
242
218
254
13
97
232
137
112
129
242
218
254
14
97
137
232
112
129
242
218
254
15
97
137
112
232
129
242
218
254
16
97
137
112
129
232
242
218
254
17
97
137
112
129
232
242
218
254
18
97
137
112
129
232
218
242
254
19
97
137
112
129
232
218
242
254
20
97
137
112
129
232
218
242
254
21
97
137
112
129
232
218
242
254
22
97
112
137
129
232
218
242
254
23
97
112
129
137
232
218
242
254
24
97
112
129
137
232
218
242
254
25
97
112
129
137
218
232
242
254
26
97
112
129
137
218
232
242
254
27
97
112
129
137
218
232
242
254
28
97
112
129
137
218
232
242
254
29
97
112
129
137
218
232
242
254
30
97
112
129
137
218
232
242
254
31
97
112
129
137
218
232
242
254


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
302
150
97
228
165
222
105
206
2
302
150
97
228
165
222
105
206
3
302
150
97
228
165
222
105
206
4
105
150
97
228
165
222
302
206
5
105
150
97
228
165
222
302
206
6
105
150
97
165
228
222
302
206
7
105
150
97
165
228
222
302
206
8
105
150
97
165
228
222
302
206
9
97
150
105
165
228
222
302
206
10
97
150
105
165
228
222
302
206
11
97
150
105
165
228
222
302
206
12
97
105
150
165
228
222
302
206
13
97
105
150
165
228
222
302
206
14
97
105
150
165
228
222
302
206
15
97
105
150
165
228
222
302
206
16
97
105
150
165
228
222
302
206
17
97
105
150
165
228
222
302
206
18
97
105
150
165
228
222
206
302
19
97
105
150
165
228
222
206
302
20
97
105
150
165
228
222
206
302
21
97
105
150
165
206
222
228
302
22
97
105
150
165
206
222
228
302
23
97
105
150
165
206
222
228
302


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


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
220

26
102
164
220
257
291
345
2
220

26
102
164
220
257
291
345
3
220

26
102
164
220
257
291
345
4
220

26
102
164
220
257
291
345
5
220

26
102
164
220
257
291
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
290

30
44
108
137
141
224
245
247
269
279
286
290
299
2
290

30
44
108
137
141
224
245
247
269
279
286
290
299
3
290

30
44
108
137
141
224
245
247
269
279
286
290
299
4
290

30
44
108
137
141
224
245
247
269
279
286
290
299
5
290

30
44
108
137
141
224
245
247
269
279
286
290
299


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!