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
207
265
176
315
151
19
164
274
2
207
265
176
315
151
19
164
274
3
207
265
176
315
151
19
164
274
4
207
176
265
315
151
19
164
274
5
176
207
265
315
151
19
164
274
6
176
207
265
315
151
19
164
274
7
176
207
265
315
151
19
164
274
8
176
207
265
151
315
19
164
274
9
176
207
151
265
315
19
164
274
10
176
151
207
265
315
19
164
274
11
151
176
207
265
315
19
164
274
12
151
176
207
265
315
19
164
274
13
151
176
207
265
19
315
164
274
14
151
176
207
19
265
315
164
274
15
151
176
19
207
265
315
164
274
16
151
19
176
207
265
315
164
274
17
19
151
176
207
265
315
164
274
18
19
151
176
207
265
315
164
274
19
19
151
176
207
265
164
315
274
20
19
151
176
207
164
265
315
274
21
19
151
176
164
207
265
315
274
22
19
151
164
176
207
265
315
274
23
19
151
164
176
207
265
315
274
24
19
151
164
176
207
265
274
315
25
19
151
164
176
207
265
274
315


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
84
182
182
243
326
133
108
62
2
84
182
182
243
326
133
108
62
3
84
182
182
243
326
133
108
62
4
84
182
182
243
326
133
108
62
5
84
182
182
243
326
133
108
62
6
84
182
182
243
326
133
108
62
7
84
182
182
243
326
133
108
62
8
84
182
182
243
133
326
108
62
9
84
182
182
243
133
108
326
62
10
84
182
182
243
133
108
62
326
11
84
182
182
243
133
108
62
326
12
84
182
182
243
133
108
62
326
13
84
182
182
243
133
108
62
326
14
84
182
182
243
133
108
62
326
15
84
182
182
243
133
108
62
326
16
84
182
182
133
243
108
62
326
17
84
182
182
133
108
243
62
326
18
84
182
182
133
108
62
243
326
19
84
182
182
133
108
62
243
326
20
84
182
182
133
108
62
243
326
21
84
182
182
133
108
62
243
326
22
84
182
182
133
108
62
243
326
23
84
182
133
182
108
62
243
326
24
84
182
133
108
182
62
243
326
25
84
182
133
108
62
182
243
326
26
84
182
133
108
62
182
243
326
27
84
182
133
108
62
182
243
326
28
84
182
133
108
62
182
243
326
29
84
133
182
108
62
182
243
326
30
84
133
108
182
62
182
243
326
31
84
133
108
62
182
182
243
326
32
84
133
108
62
182
182
243
326
33
84
133
108
62
182
182
243
326
34
84
133
108
62
182
182
243
326
35
84
108
133
62
182
182
243
326
36
84
108
62
133
182
182
243
326
37
84
108
62
133
182
182
243
326
38
84
108
62
133
182
182
243
326
39
84
108
62
133
182
182
243
326
40
84
62
108
133
182
182
243
326
41
84
62
108
133
182
182
243
326
42
84
62
108
133
182
182
243
326
43
62
84
108
133
182
182
243
326
44
62
84
108
133
182
182
243
326
45
62
84
108
133
182
182
243
326


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
238
338
23
50
193
269
267
353
2
238
338
23
50
193
269
267
353
3
238
338
23
50
193
269
267
353
4
193
338
23
50
238
269
267
353
5
193
338
23
50
238
269
267
353
6
193
50
23
338
238
269
267
353
7
193
50
23
338
238
269
267
353
8
193
50
23
338
238
269
267
353
9
23
50
193
338
238
269
267
353
10
23
50
193
338
238
269
267
353
11
23
50
193
338
238
269
267
353
12
23
50
193
338
238
269
267
353
13
23
50
193
338
238
269
267
353
14
23
50
193
267
238
269
338
353
15
23
50
193
267
238
269
338
353
16
23
50
193
267
238
269
338
353
17
23
50
193
267
238
269
338
353
18
23
50
193
267
238
269
338
353
19
23
50
193
238
267
269
338
353
20
23
50
193
238
267
269
338
353
21
23
50
193
238
267
269
338
353
22
23
50
193
238
267
269
338
353


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
212
161
232
167
283
267
97
220
2
212
161
232
167
283
267
97
220
3
212
161
232
220
283
267
97
167
4
212
161
232
220
283
267
97
167
5
212
161
283
220
232
267
97
167
6
212
161
283
220
232
267
97
167
7
212
283
161
220
232
267
97
167
8
212
283
161
220
232
267
97
167
9
212
283
267
220
232
161
97
167
10
212
283
267
220
232
161
97
167
11
283
212
267
220
232
161
97
167
12
283
212
267
220
232
161
97
167
13
283
267
212
220
232
161
97
167
14
283
267
212
220
232
161
97
167
15
283
267
232
220
212
161
97
167
16
283
267
232
220
212
161
97
167
17
167
267
232
220
212
161
97
283
18
167
267
232
220
212
161
97
283
19
267
167
232
220
212
161
97
283
20
267
167
232
220
212
161
97
283
21
267
232
167
220
212
161
97
283
22
267
232
167
220
212
161
97
283
23
267
232
212
220
167
161
97
283
24
267
232
212
220
167
161
97
283
25
97
232
212
220
167
161
267
283
26
97
232
212
220
167
161
267
283
27
232
97
212
220
167
161
267
283
28
232
97
212
220
167
161
267
283
29
232
220
212
97
167
161
267
283
30
232
220
212
97
167
161
267
283
31
161
220
212
97
167
232
267
283
32
161
220
212
97
167
232
267
283
33
220
161
212
97
167
232
267
283
34
220
161
212
97
167
232
267
283
35
220
212
161
97
167
232
267
283
36
220
212
161
97
167
232
267
283
37
220
212
167
97
161
232
267
283
38
220
212
167
97
161
232
267
283
39
161
212
167
97
220
232
267
283
40
161
212
167
97
220
232
267
283
41
212
161
167
97
220
232
267
283
42
212
161
167
97
220
232
267
283
43
212
167
161
97
220
232
267
283
44
212
167
161
97
220
232
267
283
45
97
167
161
212
220
232
267
283
46
97
167
161
212
220
232
267
283
47
167
97
161
212
220
232
267
283
48
167
97
161
212
220
232
267
283
49
167
161
97
212
220
232
267
283
50
167
161
97
212
220
232
267
283
51
97
161
167
212
220
232
267
283
52
97
161
167
212
220
232
267
283
53
161
97
167
212
220
232
267
283
54
161
97
167
212
220
232
267
283
55
97
161
167
212
220
232
267
283


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
256

73
161
207
236
256
265
315
2
256

73
161
207
236
256
265
315
3
256

73
161
207
236
256
265
315
4
256

73
161
207
236
256
265
315
5
256

73
161
207
236
256
265
315
6
256

73
161
207
236
256
265
315


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
285

38
70
76
76
234
257
260
285
301
301
325
345
350
2
285

38
70
76
76
234
257
260
285
301
301
325
345
350
3
285

38
70
76
76
234
257
260
285
301
301
325
345
350
4
285

38
70
76
76
234
257
260
285
301
301
325
345
350
5
285

38
70
76
76
234
257
260
285
301
301
325
345
350


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!