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
89
269
269
295
303
211
175
273
2
89
269
269
295
303
211
175
273
3
89
269
269
295
303
211
175
273
4
89
269
269
295
303
211
175
273
5
89
269
269
295
303
211
175
273
6
89
269
269
295
303
211
175
273
7
89
269
269
295
211
303
175
273
8
89
269
269
211
295
303
175
273
9
89
269
211
269
295
303
175
273
10
89
211
269
269
295
303
175
273
11
89
211
269
269
295
303
175
273
12
89
211
269
269
295
175
303
273
13
89
211
269
269
175
295
303
273
14
89
211
269
175
269
295
303
273
15
89
211
175
269
269
295
303
273
16
89
175
211
269
269
295
303
273
17
89
175
211
269
269
295
303
273
18
89
175
211
269
269
295
273
303
19
89
175
211
269
269
273
295
303
20
89
175
211
269
269
273
295
303


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
88
249
65
334
159
311
273
160
2
88
249
65
334
159
311
273
160
3
88
249
65
334
159
311
273
160
4
88
249
65
334
159
311
273
160
5
88
65
249
334
159
311
273
160
6
88
65
249
334
159
311
273
160
7
88
65
249
159
334
311
273
160
8
88
65
249
159
311
334
273
160
9
88
65
249
159
311
273
334
160
10
88
65
249
159
311
273
160
334
11
88
65
249
159
311
273
160
334
12
88
65
249
159
311
273
160
334
13
65
88
249
159
311
273
160
334
14
65
88
249
159
311
273
160
334
15
65
88
159
249
311
273
160
334
16
65
88
159
249
311
273
160
334
17
65
88
159
249
273
311
160
334
18
65
88
159
249
273
160
311
334
19
65
88
159
249
273
160
311
334
20
65
88
159
249
273
160
311
334
21
65
88
159
249
273
160
311
334
22
65
88
159
249
273
160
311
334
23
65
88
159
249
273
160
311
334
24
65
88
159
249
273
160
311
334
25
65
88
159
249
160
273
311
334
26
65
88
159
249
160
273
311
334
27
65
88
159
249
160
273
311
334
28
65
88
159
249
160
273
311
334
29
65
88
159
249
160
273
311
334
30
65
88
159
249
160
273
311
334
31
65
88
159
160
249
273
311
334
32
65
88
159
160
249
273
311
334
33
65
88
159
160
249
273
311
334
34
65
88
159
160
249
273
311
334
35
65
88
159
160
249
273
311
334
36
65
88
159
160
249
273
311
334


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
254
162
115
202
236
302
297
358
2
254
162
115
202
236
302
297
358
3
254
162
115
202
236
302
297
358
4
236
162
115
202
254
302
297
358
5
236
162
115
202
254
302
297
358
6
236
162
115
202
254
302
297
358
7
115
162
236
202
254
302
297
358
8
115
162
236
202
254
302
297
358
9
115
162
236
202
254
302
297
358
10
115
162
202
236
254
302
297
358
11
115
162
202
236
254
302
297
358
12
115
162
202
236
254
302
297
358
13
115
162
202
236
254
302
297
358
14
115
162
202
236
254
302
297
358
15
115
162
202
236
254
302
297
358
16
115
162
202
236
254
297
302
358
17
115
162
202
236
254
297
302
358
18
115
162
202
236
254
297
302
358
19
115
162
202
236
254
297
302
358
20
115
162
202
236
254
297
302
358
21
115
162
202
236
254
297
302
358
22
115
162
202
236
254
297
302
358


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


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
181

48
123
177
181
183
243
350
2
181

48
123
177
181
183
243
350
3
181

48
123
177
181
183
243
350
4
181

48
123
177
181
183
243
350
5
181

48
123
177
181
183
243
350


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

65
181
238
245
257
280
280
282
290
290
308
330
357
2
290

65
181
238
245
257
280
280
282
290
290
308
330
357
3
290

65
181
238
245
257
280
280
282
290
290
308
330
357
4
290

65
181
238
245
257
280
280
282
290
290
308
330
357


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!