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
130
53
14
321
197
236
49
78
2
130
53
14
321
197
236
49
78
3
53
130
14
321
197
236
49
78
4
53
130
14
321
197
236
49
78
5
53
14
130
321
197
236
49
78
6
14
53
130
321
197
236
49
78
7
14
53
130
321
197
236
49
78
8
14
53
130
321
197
236
49
78
9
14
53
130
197
321
236
49
78
10
14
53
130
197
321
236
49
78
11
14
53
130
197
236
321
49
78
12
14
53
130
197
236
321
49
78
13
14
53
130
197
236
49
321
78
14
14
53
130
197
49
236
321
78
15
14
53
130
49
197
236
321
78
16
14
53
49
130
197
236
321
78
17
14
49
53
130
197
236
321
78
18
14
49
53
130
197
236
321
78
19
14
49
53
130
197
236
78
321
20
14
49
53
130
197
78
236
321
21
14
49
53
130
78
197
236
321
22
14
49
53
78
130
197
236
321
23
14
49
53
78
130
197
236
321


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
32
198
173
10
102
324
71
45
2
32
198
173
10
102
324
71
45
3
32
198
173
10
102
324
71
45
4
32
198
173
10
102
324
71
45
5
32
173
198
10
102
324
71
45
6
32
173
10
198
102
324
71
45
7
32
173
10
102
198
324
71
45
8
32
173
10
102
198
324
71
45
9
32
173
10
102
198
71
324
45
10
32
173
10
102
198
71
45
324
11
32
173
10
102
198
71
45
324
12
32
173
10
102
198
71
45
324
13
32
173
10
102
198
71
45
324
14
32
10
173
102
198
71
45
324
15
32
10
102
173
198
71
45
324
16
32
10
102
173
198
71
45
324
17
32
10
102
173
71
198
45
324
18
32
10
102
173
71
45
198
324
19
32
10
102
173
71
45
198
324
20
32
10
102
173
71
45
198
324
21
10
32
102
173
71
45
198
324
22
10
32
102
173
71
45
198
324
23
10
32
102
173
71
45
198
324
24
10
32
102
71
173
45
198
324
25
10
32
102
71
45
173
198
324
26
10
32
102
71
45
173
198
324
27
10
32
102
71
45
173
198
324
28
10
32
102
71
45
173
198
324
29
10
32
102
71
45
173
198
324
30
10
32
71
102
45
173
198
324
31
10
32
71
45
102
173
198
324
32
10
32
71
45
102
173
198
324
33
10
32
71
45
102
173
198
324
34
10
32
71
45
102
173
198
324
35
10
32
71
45
102
173
198
324
36
10
32
45
71
102
173
198
324
37
10
32
45
71
102
173
198
324
38
10
32
45
71
102
173
198
324
39
10
32
45
71
102
173
198
324
40
10
32
45
71
102
173
198
324


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
304
291
351
207
127
217
194
280
2
304
291
351
207
127
217
194
280
3
304
291
351
207
127
217
194
280
4
127
291
351
207
304
217
194
280
5
127
291
351
207
304
217
194
280
6
127
291
351
207
304
217
194
280
7
127
291
280
207
304
217
194
351
8
127
291
280
207
304
217
194
351
9
127
291
280
207
194
217
304
351
10
127
291
280
207
194
217
304
351
11
127
291
280
207
194
217
304
351
12
127
194
280
207
291
217
304
351
13
127
194
280
207
291
217
304
351
14
127
194
207
280
291
217
304
351
15
127
194
207
280
291
217
304
351
16
127
194
207
280
291
217
304
351
17
127
194
207
280
291
217
304
351
18
127
194
207
280
291
217
304
351
19
127
194
207
280
291
217
304
351
20
127
194
207
280
217
291
304
351
21
127
194
207
280
217
291
304
351
22
127
194
207
280
217
291
304
351
23
127
194
207
217
280
291
304
351
24
127
194
207
217
280
291
304
351
25
127
194
207
217
280
291
304
351
26
127
194
207
217
280
291
304
351


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
217
165
73
84
269
110
32
2
341
217
165
73
84
269
110
32
3
341
217
165
110
84
269
73
32
4
341
217
165
110
84
269
73
32
5
341
217
269
110
84
165
73
32
6
341
217
269
110
84
165
73
32
7
341
269
217
110
84
165
73
32
8
341
269
217
110
84
165
73
32
9
32
269
217
110
84
165
73
341
10
32
269
217
110
84
165
73
341
11
269
32
217
110
84
165
73
341
12
269
32
217
110
84
165
73
341
13
269
217
32
110
84
165
73
341
14
269
217
32
110
84
165
73
341
15
269
217
165
110
84
32
73
341
16
269
217
165
110
84
32
73
341
17
73
217
165
110
84
32
269
341
18
73
217
165
110
84
32
269
341
19
217
73
165
110
84
32
269
341
20
217
73
165
110
84
32
269
341
21
217
165
73
110
84
32
269
341
22
217
165
73
110
84
32
269
341
23
217
165
84
110
73
32
269
341
24
217
165
84
110
73
32
269
341
25
32
165
84
110
73
217
269
341
26
32
165
84
110
73
217
269
341
27
165
32
84
110
73
217
269
341
28
165
32
84
110
73
217
269
341
29
165
110
84
32
73
217
269
341
30
165
110
84
32
73
217
269
341
31
73
110
84
32
165
217
269
341
32
73
110
84
32
165
217
269
341
33
110
73
84
32
165
217
269
341
34
110
73
84
32
165
217
269
341
35
110
84
73
32
165
217
269
341
36
110
84
73
32
165
217
269
341
37
32
84
73
110
165
217
269
341
38
32
84
73
110
165
217
269
341
39
84
32
73
110
165
217
269
341
40
84
32
73
110
165
217
269
341
41
84
73
32
110
165
217
269
341
42
84
73
32
110
165
217
269
341
43
32
73
84
110
165
217
269
341
44
32
73
84
110
165
217
269
341
45
73
32
84
110
165
217
269
341
46
73
32
84
110
165
217
269
341
47
32
73
84
110
165
217
269
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
275

71
90
97
170
173
183
275
2
275

71
90
97
170
173
183
275
3
275

71
90
97
170
173
183
275
4
275

71
90
97
170
173
183
275
5
275

71
90
97
170
173
183
275
6
275

71
90
97
170
173
183
275
7
275

71
90
97
170
173
183
275
8
275

71
90
97
170
173
183
275


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
306

11
43
49
76
105
114
134
165
169
187
190
223
306
2
306

11
43
49
76
105
114
134
165
169
187
190
223
306
3
306

11
43
49
76
105
114
134
165
169
187
190
223
306
4
306

11
43
49
76
105
114
134
165
169
187
190
223
306


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!