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
211
222
110
302
4
132
141
344
2
211
222
110
302
4
132
141
344
3
211
222
110
302
4
132
141
344
4
211
110
222
302
4
132
141
344
5
110
211
222
302
4
132
141
344
6
110
211
222
302
4
132
141
344
7
110
211
222
302
4
132
141
344
8
110
211
222
4
302
132
141
344
9
110
211
4
222
302
132
141
344
10
110
4
211
222
302
132
141
344
11
4
110
211
222
302
132
141
344
12
4
110
211
222
302
132
141
344
13
4
110
211
222
132
302
141
344
14
4
110
211
132
222
302
141
344
15
4
110
132
211
222
302
141
344
16
4
110
132
211
222
302
141
344
17
4
110
132
211
222
141
302
344
18
4
110
132
211
141
222
302
344
19
4
110
132
141
211
222
302
344
20
4
110
132
141
211
222
302
344
21
4
110
132
141
211
222
302
344


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
48
5
22
249
312
30
204
325
2
48
5
22
249
312
30
204
325
3
48
5
22
249
312
30
204
325
4
5
48
22
249
312
30
204
325
5
5
22
48
249
312
30
204
325
6
5
22
48
249
312
30
204
325
7
5
22
48
249
312
30
204
325
8
5
22
48
249
30
312
204
325
9
5
22
48
249
30
204
312
325
10
5
22
48
249
30
204
312
325
11
5
22
48
249
30
204
312
325
12
5
22
48
249
30
204
312
325
13
5
22
48
249
30
204
312
325
14
5
22
48
249
30
204
312
325
15
5
22
48
249
30
204
312
325
16
5
22
48
30
249
204
312
325
17
5
22
48
30
204
249
312
325
18
5
22
48
30
204
249
312
325
19
5
22
48
30
204
249
312
325
20
5
22
48
30
204
249
312
325
21
5
22
48
30
204
249
312
325
22
5
22
48
30
204
249
312
325
23
5
22
30
48
204
249
312
325
24
5
22
30
48
204
249
312
325
25
5
22
30
48
204
249
312
325
26
5
22
30
48
204
249
312
325
27
5
22
30
48
204
249
312
325
28
5
22
30
48
204
249
312
325
29
5
22
30
48
204
249
312
325
30
5
22
30
48
204
249
312
325
31
5
22
30
48
204
249
312
325


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
168
269
290
338
25
37
104
265
2
168
269
290
338
25
37
104
265
3
168
269
290
338
25
37
104
265
4
25
269
290
338
168
37
104
265
5
25
269
290
338
168
37
104
265
6
25
269
290
338
168
37
104
265
7
25
104
290
338
168
37
269
265
8
25
104
290
338
168
37
269
265
9
25
104
37
338
168
290
269
265
10
25
104
37
338
168
290
269
265
11
25
104
37
168
338
290
269
265
12
25
104
37
168
338
290
269
265
13
25
104
37
168
338
290
269
265
14
25
37
104
168
338
290
269
265
15
25
37
104
168
338
290
269
265
16
25
37
104
168
338
290
269
265
17
25
37
104
168
338
290
269
265
18
25
37
104
168
338
290
269
265
19
25
37
104
168
338
290
269
265
20
25
37
104
168
265
290
269
338
21
25
37
104
168
265
290
269
338
22
25
37
104
168
265
269
290
338
23
25
37
104
168
265
269
290
338
24
25
37
104
168
265
269
290
338
25
25
37
104
168
265
269
290
338
26
25
37
104
168
265
269
290
338
27
25
37
104
168
265
269
290
338
28
25
37
104
168
265
269
290
338


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


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
259

148
187
189
210
259
301
335
2
259

148
187
189
210
259
301
335
3
259

148
187
189
210
259
301
335
4
259

148
187
189
210
259
301
335
5
259

148
187
189
210
259
301
335
6
259

148
187
189
210
259
301
335


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
31

24
31
79
124
124
157
165
177
195
195
252
271
288
2
31

24
31
79
124
124
157
165
177
195
195
252
271
288
3
31

24
31
79
124
124
157
165
177
195
195
252
271
288
4
31

24
31
79
124
124
157
165
177
195
195
252
271
288
5
31

24
31
79
124
124
157
165
177
195
195
252
271
288


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!