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
219
325
315
233
110
65
349
18
2
219
325
315
233
110
65
349
18
3
219
325
315
233
110
65
349
18
4
219
315
325
233
110
65
349
18
5
219
315
325
233
110
65
349
18
6
219
315
233
325
110
65
349
18
7
219
233
315
325
110
65
349
18
8
219
233
315
325
110
65
349
18
9
219
233
315
110
325
65
349
18
10
219
233
110
315
325
65
349
18
11
219
110
233
315
325
65
349
18
12
110
219
233
315
325
65
349
18
13
110
219
233
315
325
65
349
18
14
110
219
233
315
65
325
349
18
15
110
219
233
65
315
325
349
18
16
110
219
65
233
315
325
349
18
17
110
65
219
233
315
325
349
18
18
65
110
219
233
315
325
349
18
19
65
110
219
233
315
325
349
18
20
65
110
219
233
315
325
349
18
21
65
110
219
233
315
325
18
349
22
65
110
219
233
315
18
325
349
23
65
110
219
233
18
315
325
349
24
65
110
219
18
233
315
325
349
25
65
110
18
219
233
315
325
349
26
65
18
110
219
233
315
325
349
27
18
65
110
219
233
315
325
349
28
18
65
110
219
233
315
325
349


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


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
233
328
205
339
335
327
298
75
2
233
328
205
339
335
327
298
75
3
233
328
205
339
335
327
298
75
4
233
328
205
75
335
327
298
339
5
233
328
205
75
335
327
298
339
6
233
328
205
75
298
327
335
339
7
233
328
205
75
298
327
335
339
8
233
328
205
75
298
327
335
339
9
75
328
205
233
298
327
335
339
10
75
328
205
233
298
327
335
339
11
75
328
205
233
298
327
335
339
12
75
233
205
328
298
327
335
339
13
75
233
205
328
298
327
335
339
14
75
233
205
328
298
327
335
339
15
75
205
233
328
298
327
335
339
16
75
205
233
328
298
327
335
339
17
75
205
233
328
298
327
335
339
18
75
205
233
298
328
327
335
339
19
75
205
233
298
328
327
335
339
20
75
205
233
298
328
327
335
339
21
75
205
233
298
327
328
335
339
22
75
205
233
298
327
328
335
339
23
75
205
233
298
327
328
335
339
24
75
205
233
298
327
328
335
339


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
195
8
116
211
317
133
225
194
2
195
8
116
211
317
133
225
194
3
195
8
116
225
317
133
211
194
4
195
8
116
225
317
133
211
194
5
195
8
317
225
116
133
211
194
6
195
8
317
225
116
133
211
194
7
195
317
8
225
116
133
211
194
8
195
317
8
225
116
133
211
194
9
195
317
133
225
116
8
211
194
10
195
317
133
225
116
8
211
194
11
317
195
133
225
116
8
211
194
12
317
195
133
225
116
8
211
194
13
317
225
133
195
116
8
211
194
14
317
225
133
195
116
8
211
194
15
317
225
133
211
116
8
195
194
16
317
225
133
211
116
8
195
194
17
194
225
133
211
116
8
195
317
18
194
225
133
211
116
8
195
317
19
225
194
133
211
116
8
195
317
20
225
194
133
211
116
8
195
317
21
225
211
133
194
116
8
195
317
22
225
211
133
194
116
8
195
317
23
225
211
133
195
116
8
194
317
24
225
211
133
195
116
8
194
317
25
194
211
133
195
116
8
225
317
26
194
211
133
195
116
8
225
317
27
211
194
133
195
116
8
225
317
28
211
194
133
195
116
8
225
317
29
211
195
133
194
116
8
225
317
30
211
195
133
194
116
8
225
317
31
8
195
133
194
116
211
225
317
32
8
195
133
194
116
211
225
317
33
195
8
133
194
116
211
225
317
34
195
8
133
194
116
211
225
317
35
195
194
133
8
116
211
225
317
36
195
194
133
8
116
211
225
317
37
116
194
133
8
195
211
225
317
38
116
194
133
8
195
211
225
317
39
194
116
133
8
195
211
225
317
40
194
116
133
8
195
211
225
317
41
194
133
116
8
195
211
225
317
42
194
133
116
8
195
211
225
317
43
8
133
116
194
195
211
225
317
44
8
133
116
194
195
211
225
317
45
133
8
116
194
195
211
225
317
46
133
8
116
194
195
211
225
317
47
133
116
8
194
195
211
225
317
48
133
116
8
194
195
211
225
317
49
8
116
133
194
195
211
225
317
50
8
116
133
194
195
211
225
317
51
116
8
133
194
195
211
225
317
52
116
8
133
194
195
211
225
317
53
8
116
133
194
195
211
225
317


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
201

111
116
158
168
197
201
278
2
201

111
116
158
168
197
201
278
3
201

111
116
158
168
197
201
278
4
201

111
116
158
168
197
201
278
5
201

111
116
158
168
197
201
278
6
201

111
116
158
168
197
201
278
7
201

111
116
158
168
197
201
278


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
316

63
70
111
118
171
172
200
213
305
316
342
346
349
2
316

63
70
111
118
171
172
200
213
305
316
342
346
349
3
316

63
70
111
118
171
172
200
213
305
316
342
346
349
4
316

63
70
111
118
171
172
200
213
305
316
342
346
349
5
316

63
70
111
118
171
172
200
213
305
316
342
346
349


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!