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
84
210
140
260
152
211
30
280
2
84
210
140
260
152
211
30
280
3
84
210
140
260
152
211
30
280
4
84
140
210
260
152
211
30
280
5
84
140
210
260
152
211
30
280
6
84
140
210
260
152
211
30
280
7
84
140
210
152
260
211
30
280
8
84
140
152
210
260
211
30
280
9
84
140
152
210
260
211
30
280
10
84
140
152
210
211
260
30
280
11
84
140
152
210
211
260
30
280
12
84
140
152
210
211
30
260
280
13
84
140
152
210
30
211
260
280
14
84
140
152
30
210
211
260
280
15
84
140
30
152
210
211
260
280
16
84
30
140
152
210
211
260
280
17
30
84
140
152
210
211
260
280
18
30
84
140
152
210
211
260
280
19
30
84
140
152
210
211
260
280


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
99
298
359
142
308
65
193
52
2
99
298
359
142
308
65
193
52
3
99
298
359
142
308
65
193
52
4
99
298
359
142
308
65
193
52
5
99
298
359
142
308
65
193
52
6
99
298
142
359
308
65
193
52
7
99
298
142
308
359
65
193
52
8
99
298
142
308
65
359
193
52
9
99
298
142
308
65
193
359
52
10
99
298
142
308
65
193
52
359
11
99
298
142
308
65
193
52
359
12
99
298
142
308
65
193
52
359
13
99
298
142
308
65
193
52
359
14
99
142
298
308
65
193
52
359
15
99
142
298
308
65
193
52
359
16
99
142
298
65
308
193
52
359
17
99
142
298
65
193
308
52
359
18
99
142
298
65
193
52
308
359
19
99
142
298
65
193
52
308
359
20
99
142
298
65
193
52
308
359
21
99
142
298
65
193
52
308
359
22
99
142
298
65
193
52
308
359
23
99
142
65
298
193
52
308
359
24
99
142
65
193
298
52
308
359
25
99
142
65
193
52
298
308
359
26
99
142
65
193
52
298
308
359
27
99
142
65
193
52
298
308
359
28
99
142
65
193
52
298
308
359
29
99
65
142
193
52
298
308
359
30
99
65
142
193
52
298
308
359
31
99
65
142
52
193
298
308
359
32
99
65
142
52
193
298
308
359
33
99
65
142
52
193
298
308
359
34
65
99
142
52
193
298
308
359
35
65
99
142
52
193
298
308
359
36
65
99
52
142
193
298
308
359
37
65
99
52
142
193
298
308
359
38
65
99
52
142
193
298
308
359
39
65
99
52
142
193
298
308
359
40
65
52
99
142
193
298
308
359
41
65
52
99
142
193
298
308
359
42
65
52
99
142
193
298
308
359
43
52
65
99
142
193
298
308
359
44
52
65
99
142
193
298
308
359
45
52
65
99
142
193
298
308
359


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
134
291
91
85
215
181
150
77
2
134
291
91
85
215
181
150
77
3
134
291
91
85
215
181
150
77
4
134
77
91
85
215
181
150
291
5
134
77
91
85
215
181
150
291
6
134
77
91
85
150
181
215
291
7
134
77
91
85
150
181
215
291
8
134
77
91
85
150
181
215
291
9
85
77
91
134
150
181
215
291
10
85
77
91
134
150
181
215
291
11
85
77
91
134
150
181
215
291
12
77
85
91
134
150
181
215
291
13
77
85
91
134
150
181
215
291
14
77
85
91
134
150
181
215
291
15
77
85
91
134
150
181
215
291
16
77
85
91
134
150
181
215
291
17
77
85
91
134
150
181
215
291
18
77
85
91
134
150
181
215
291
19
77
85
91
134
150
181
215
291
20
77
85
91
134
150
181
215
291
21
77
85
91
134
150
181
215
291


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


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
223

16
22
34
223
239
239
323
2
223

16
22
34
223
239
239
323
3
223

16
22
34
223
239
239
323
4
223

16
22
34
223
239
239
323
5
223

16
22
34
223
239
239
323


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
320

71
72
83
93
124
212
248
259
298
313
320
353
353
2
320

71
72
83
93
124
212
248
259
298
313
320
353
353
3
320

71
72
83
93
124
212
248
259
298
313
320
353
353


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!