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
301
14
200
168
113
58
86
162
2
301
14
200
168
113
58
86
162
3
14
301
200
168
113
58
86
162
4
14
301
200
168
113
58
86
162
5
14
200
301
168
113
58
86
162
6
14
200
301
168
113
58
86
162
7
14
200
168
301
113
58
86
162
8
14
168
200
301
113
58
86
162
9
14
168
200
301
113
58
86
162
10
14
168
200
113
301
58
86
162
11
14
168
113
200
301
58
86
162
12
14
113
168
200
301
58
86
162
13
14
113
168
200
301
58
86
162
14
14
113
168
200
58
301
86
162
15
14
113
168
58
200
301
86
162
16
14
113
58
168
200
301
86
162
17
14
58
113
168
200
301
86
162
18
14
58
113
168
200
301
86
162
19
14
58
113
168
200
86
301
162
20
14
58
113
168
86
200
301
162
21
14
58
113
86
168
200
301
162
22
14
58
86
113
168
200
301
162
23
14
58
86
113
168
200
301
162
24
14
58
86
113
168
200
162
301
25
14
58
86
113
168
162
200
301
26
14
58
86
113
162
168
200
301
27
14
58
86
113
162
168
200
301


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


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
211
336
48
232
46
54
226
299
2
211
336
48
232
46
54
226
299
3
211
336
48
232
46
54
226
299
4
46
336
48
232
211
54
226
299
5
46
336
48
232
211
54
226
299
6
46
336
48
232
211
54
226
299
7
46
54
48
232
211
336
226
299
8
46
54
48
232
211
336
226
299
9
46
54
48
211
232
336
226
299
10
46
54
48
211
232
336
226
299
11
46
54
48
211
232
336
226
299
12
46
48
54
211
232
336
226
299
13
46
48
54
211
232
336
226
299
14
46
48
54
211
232
336
226
299
15
46
48
54
211
232
336
226
299
16
46
48
54
211
232
336
226
299
17
46
48
54
211
232
336
226
299
18
46
48
54
211
226
336
232
299
19
46
48
54
211
226
336
232
299
20
46
48
54
211
226
336
232
299
21
46
48
54
211
226
232
336
299
22
46
48
54
211
226
232
336
299
23
46
48
54
211
226
232
336
299
24
46
48
54
211
226
232
299
336


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
351
46
19
134
300
45
340
339
2
351
46
19
134
300
45
340
339
3
351
46
19
340
300
45
134
339
4
351
46
19
340
300
45
134
339
5
351
46
300
340
19
45
134
339
6
351
46
300
340
19
45
134
339
7
351
340
300
46
19
45
134
339
8
351
340
300
46
19
45
134
339
9
351
340
300
339
19
45
134
46
10
351
340
300
339
19
45
134
46
11
46
340
300
339
19
45
134
351
12
46
340
300
339
19
45
134
351
13
340
46
300
339
19
45
134
351
14
340
46
300
339
19
45
134
351
15
340
339
300
46
19
45
134
351
16
340
339
300
46
19
45
134
351
17
340
339
300
134
19
45
46
351
18
340
339
300
134
19
45
46
351
19
46
339
300
134
19
45
340
351
20
46
339
300
134
19
45
340
351
21
339
46
300
134
19
45
340
351
22
339
46
300
134
19
45
340
351
23
339
300
46
134
19
45
340
351
24
339
300
46
134
19
45
340
351
25
45
300
46
134
19
339
340
351
26
45
300
46
134
19
339
340
351
27
300
45
46
134
19
339
340
351
28
300
45
46
134
19
339
340
351
29
300
134
46
45
19
339
340
351
30
300
134
46
45
19
339
340
351
31
19
134
46
45
300
339
340
351
32
19
134
46
45
300
339
340
351
33
134
19
46
45
300
339
340
351
34
134
19
46
45
300
339
340
351
35
134
46
19
45
300
339
340
351
36
134
46
19
45
300
339
340
351
37
45
46
19
134
300
339
340
351
38
45
46
19
134
300
339
340
351
39
46
45
19
134
300
339
340
351
40
46
45
19
134
300
339
340
351
41
19
45
46
134
300
339
340
351
42
19
45
46
134
300
339
340
351
43
45
19
46
134
300
339
340
351
44
45
19
46
134
300
339
340
351
45
19
45
46
134
300
339
340
351


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
244

5
11
69
244
262
283
298
2
244

5
11
69
244
262
283
298
3
244

5
11
69
244
262
283
298
4
244

5
11
69
244
262
283
298
5
244

5
11
69
244
262
283
298


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
207

75
79
82
122
125
206
207
268
271
282
289
304
346
2
207

75
79
82
122
125
206
207
268
271
282
289
304
346


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!