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
73
269
255
177
331
109
305
82
2
73
269
255
177
331
109
305
82
3
73
269
255
177
331
109
305
82
4
73
255
269
177
331
109
305
82
5
73
255
269
177
331
109
305
82
6
73
255
177
269
331
109
305
82
7
73
177
255
269
331
109
305
82
8
73
177
255
269
331
109
305
82
9
73
177
255
269
331
109
305
82
10
73
177
255
269
109
331
305
82
11
73
177
255
109
269
331
305
82
12
73
177
109
255
269
331
305
82
13
73
109
177
255
269
331
305
82
14
73
109
177
255
269
331
305
82
15
73
109
177
255
269
305
331
82
16
73
109
177
255
269
305
331
82
17
73
109
177
255
269
305
82
331
18
73
109
177
255
269
82
305
331
19
73
109
177
255
82
269
305
331
20
73
109
177
82
255
269
305
331
21
73
109
82
177
255
269
305
331
22
73
82
109
177
255
269
305
331
23
73
82
109
177
255
269
305
331


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
196
326
73
343
107
212
218
85
2
196
326
73
343
107
212
218
85
3
196
326
73
343
107
212
218
85
4
196
326
73
343
107
212
218
85
5
196
73
326
343
107
212
218
85
6
196
73
326
343
107
212
218
85
7
196
73
326
107
343
212
218
85
8
196
73
326
107
212
343
218
85
9
196
73
326
107
212
218
343
85
10
196
73
326
107
212
218
85
343
11
196
73
326
107
212
218
85
343
12
196
73
326
107
212
218
85
343
13
73
196
326
107
212
218
85
343
14
73
196
326
107
212
218
85
343
15
73
196
107
326
212
218
85
343
16
73
196
107
212
326
218
85
343
17
73
196
107
212
218
326
85
343
18
73
196
107
212
218
85
326
343
19
73
196
107
212
218
85
326
343
20
73
196
107
212
218
85
326
343
21
73
196
107
212
218
85
326
343
22
73
107
196
212
218
85
326
343
23
73
107
196
212
218
85
326
343
24
73
107
196
212
218
85
326
343
25
73
107
196
212
85
218
326
343
26
73
107
196
212
85
218
326
343
27
73
107
196
212
85
218
326
343
28
73
107
196
212
85
218
326
343
29
73
107
196
212
85
218
326
343
30
73
107
196
212
85
218
326
343
31
73
107
196
85
212
218
326
343
32
73
107
196
85
212
218
326
343
33
73
107
196
85
212
218
326
343
34
73
107
196
85
212
218
326
343
35
73
107
196
85
212
218
326
343
36
73
107
85
196
212
218
326
343
37
73
107
85
196
212
218
326
343
38
73
107
85
196
212
218
326
343
39
73
107
85
196
212
218
326
343
40
73
85
107
196
212
218
326
343
41
73
85
107
196
212
218
326
343
42
73
85
107
196
212
218
326
343
43
73
85
107
196
212
218
326
343


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
78
51
252
248
329
191
320
335
2
78
51
252
248
329
191
320
335
3
78
51
252
248
329
191
320
335
4
78
51
252
248
320
191
329
335
5
78
51
252
248
320
191
329
335
6
78
51
252
248
320
191
329
335
7
78
51
191
248
320
252
329
335
8
78
51
191
248
320
252
329
335
9
78
51
191
248
320
252
329
335
10
78
51
191
248
320
252
329
335
11
78
51
191
248
320
252
329
335
12
51
78
191
248
320
252
329
335
13
51
78
191
248
320
252
329
335
14
51
78
191
248
320
252
329
335
15
51
78
191
248
320
252
329
335
16
51
78
191
248
320
252
329
335
17
51
78
191
248
320
252
329
335
18
51
78
191
248
252
320
329
335
19
51
78
191
248
252
320
329
335
20
51
78
191
248
252
320
329
335
21
51
78
191
248
252
320
329
335


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
234
89
60
274
93
297
96
119
2
234
89
60
274
93
297
96
119
3
234
89
297
274
93
60
96
119
4
234
89
297
274
93
60
96
119
5
234
297
89
274
93
60
96
119
6
234
297
89
274
93
60
96
119
7
234
297
93
274
89
60
96
119
8
234
297
93
274
89
60
96
119
9
297
234
93
274
89
60
96
119
10
297
234
93
274
89
60
96
119
11
297
274
93
234
89
60
96
119
12
297
274
93
234
89
60
96
119
13
119
274
93
234
89
60
96
297
14
119
274
93
234
89
60
96
297
15
274
119
93
234
89
60
96
297
16
274
119
93
234
89
60
96
297
17
274
234
93
119
89
60
96
297
18
274
234
93
119
89
60
96
297
19
96
234
93
119
89
60
274
297
20
96
234
93
119
89
60
274
297
21
234
96
93
119
89
60
274
297
22
234
96
93
119
89
60
274
297
23
234
119
93
96
89
60
274
297
24
234
119
93
96
89
60
274
297
25
60
119
93
96
89
234
274
297
26
60
119
93
96
89
234
274
297
27
119
60
93
96
89
234
274
297
28
119
60
93
96
89
234
274
297
29
119
96
93
60
89
234
274
297
30
119
96
93
60
89
234
274
297
31
89
96
93
60
119
234
274
297
32
89
96
93
60
119
234
274
297
33
96
89
93
60
119
234
274
297
34
96
89
93
60
119
234
274
297
35
96
93
89
60
119
234
274
297
36
96
93
89
60
119
234
274
297
37
60
93
89
96
119
234
274
297
38
60
93
89
96
119
234
274
297
39
93
60
89
96
119
234
274
297
40
93
60
89
96
119
234
274
297
41
93
89
60
96
119
234
274
297
42
93
89
60
96
119
234
274
297
43
60
89
93
96
119
234
274
297
44
60
89
93
96
119
234
274
297
45
89
60
93
96
119
234
274
297
46
89
60
93
96
119
234
274
297
47
60
89
93
96
119
234
274
297


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
112

85
112
208
214
267
272
324
2
112

85
112
208
214
267
272
324
3
112

85
112
208
214
267
272
324


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
241

57
68
152
188
205
222
236
241
263
266
286
322
326
2
241

57
68
152
188
205
222
236
241
263
266
286
322
326
3
241

57
68
152
188
205
222
236
241
263
266
286
322
326
4
241

57
68
152
188
205
222
236
241
263
266
286
322
326
5
241

57
68
152
188
205
222
236
241
263
266
286
322
326


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!