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
302
57
278
5
75
41
179
241
2
302
57
278
5
75
41
179
241
3
57
302
278
5
75
41
179
241
4
57
302
278
5
75
41
179
241
5
57
278
302
5
75
41
179
241
6
57
278
302
5
75
41
179
241
7
57
278
5
302
75
41
179
241
8
57
5
278
302
75
41
179
241
9
5
57
278
302
75
41
179
241
10
5
57
278
302
75
41
179
241
11
5
57
278
75
302
41
179
241
12
5
57
75
278
302
41
179
241
13
5
57
75
278
302
41
179
241
14
5
57
75
278
41
302
179
241
15
5
57
75
41
278
302
179
241
16
5
57
41
75
278
302
179
241
17
5
41
57
75
278
302
179
241
18
5
41
57
75
278
302
179
241
19
5
41
57
75
278
179
302
241
20
5
41
57
75
179
278
302
241
21
5
41
57
75
179
278
302
241
22
5
41
57
75
179
278
241
302
23
5
41
57
75
179
241
278
302
24
5
41
57
75
179
241
278
302


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
253
5
202
11
40
110
151
37
2
253
5
202
11
40
110
151
37
3
253
5
202
11
40
110
151
37
4
5
253
202
11
40
110
151
37
5
5
202
253
11
40
110
151
37
6
5
202
11
253
40
110
151
37
7
5
202
11
40
253
110
151
37
8
5
202
11
40
110
253
151
37
9
5
202
11
40
110
151
253
37
10
5
202
11
40
110
151
37
253
11
5
202
11
40
110
151
37
253
12
5
202
11
40
110
151
37
253
13
5
202
11
40
110
151
37
253
14
5
11
202
40
110
151
37
253
15
5
11
40
202
110
151
37
253
16
5
11
40
110
202
151
37
253
17
5
11
40
110
151
202
37
253
18
5
11
40
110
151
37
202
253
19
5
11
40
110
151
37
202
253
20
5
11
40
110
151
37
202
253
21
5
11
40
110
151
37
202
253
22
5
11
40
110
151
37
202
253
23
5
11
40
110
151
37
202
253
24
5
11
40
110
151
37
202
253
25
5
11
40
110
37
151
202
253
26
5
11
40
110
37
151
202
253
27
5
11
40
110
37
151
202
253
28
5
11
40
110
37
151
202
253
29
5
11
40
110
37
151
202
253
30
5
11
40
110
37
151
202
253
31
5
11
40
37
110
151
202
253
32
5
11
40
37
110
151
202
253
33
5
11
40
37
110
151
202
253
34
5
11
40
37
110
151
202
253
35
5
11
40
37
110
151
202
253
36
5
11
37
40
110
151
202
253
37
5
11
37
40
110
151
202
253
38
5
11
37
40
110
151
202
253
39
5
11
37
40
110
151
202
253
40
5
11
37
40
110
151
202
253


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
305
155
360
8
342
249
34
143
2
305
155
360
8
342
249
34
143
3
305
155
360
8
342
249
34
143
4
305
155
143
8
342
249
34
360
5
305
155
143
8
342
249
34
360
6
305
155
143
8
34
249
342
360
7
305
155
143
8
34
249
342
360
8
305
155
143
8
34
249
342
360
9
8
155
143
305
34
249
342
360
10
8
155
143
305
34
249
342
360
11
8
155
143
305
34
249
342
360
12
8
155
143
249
34
305
342
360
13
8
155
143
249
34
305
342
360
14
8
155
143
249
34
305
342
360
15
8
155
143
34
249
305
342
360
16
8
155
143
34
249
305
342
360
17
8
155
143
34
249
305
342
360
18
8
34
143
155
249
305
342
360
19
8
34
143
155
249
305
342
360
20
8
34
143
155
249
305
342
360
21
8
34
143
155
249
305
342
360
22
8
34
143
155
249
305
342
360
23
8
34
143
155
249
305
342
360


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


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
150

47
80
150
150
305
315
360
2
150

47
80
150
150
305
315
360
3
150

47
80
150
150
305
315
360
4
150

47
80
150
150
305
315
360


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
359

24
26
45
67
143
177
185
243
248
259
321
325
359
2
359

24
26
45
67
143
177
185
243
248
259
321
325
359
3
359

24
26
45
67
143
177
185
243
248
259
321
325
359
4
359

24
26
45
67
143
177
185
243
248
259
321
325
359


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!