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
100
29
324
237
138
140
288
80
2
100
29
324
237
138
140
288
80
3
29
100
324
237
138
140
288
80
4
29
100
324
237
138
140
288
80
5
29
100
324
237
138
140
288
80
6
29
100
237
324
138
140
288
80
7
29
100
237
324
138
140
288
80
8
29
100
237
138
324
140
288
80
9
29
100
138
237
324
140
288
80
10
29
100
138
237
324
140
288
80
11
29
100
138
237
140
324
288
80
12
29
100
138
140
237
324
288
80
13
29
100
138
140
237
324
288
80
14
29
100
138
140
237
288
324
80
15
29
100
138
140
237
288
324
80
16
29
100
138
140
237
288
80
324
17
29
100
138
140
237
80
288
324
18
29
100
138
140
80
237
288
324
19
29
100
138
80
140
237
288
324
20
29
100
80
138
140
237
288
324
21
29
80
100
138
140
237
288
324
22
29
80
100
138
140
237
288
324


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
7
38
156
347
115
27
31
282
2
7
38
156
347
115
27
31
282
3
7
38
156
347
115
27
31
282
4
7
38
156
347
115
27
31
282
5
7
38
156
347
115
27
31
282
6
7
38
156
347
115
27
31
282
7
7
38
156
115
347
27
31
282
8
7
38
156
115
27
347
31
282
9
7
38
156
115
27
31
347
282
10
7
38
156
115
27
31
282
347
11
7
38
156
115
27
31
282
347
12
7
38
156
115
27
31
282
347
13
7
38
156
115
27
31
282
347
14
7
38
156
115
27
31
282
347
15
7
38
115
156
27
31
282
347
16
7
38
115
27
156
31
282
347
17
7
38
115
27
31
156
282
347
18
7
38
115
27
31
156
282
347
19
7
38
115
27
31
156
282
347
20
7
38
115
27
31
156
282
347
21
7
38
115
27
31
156
282
347
22
7
38
115
27
31
156
282
347
23
7
38
27
115
31
156
282
347
24
7
38
27
31
115
156
282
347
25
7
38
27
31
115
156
282
347
26
7
38
27
31
115
156
282
347
27
7
38
27
31
115
156
282
347
28
7
38
27
31
115
156
282
347
29
7
27
38
31
115
156
282
347
30
7
27
31
38
115
156
282
347
31
7
27
31
38
115
156
282
347
32
7
27
31
38
115
156
282
347
33
7
27
31
38
115
156
282
347
34
7
27
31
38
115
156
282
347
35
7
27
31
38
115
156
282
347
36
7
27
31
38
115
156
282
347


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
73
50
215
354
109
23
17
216
2
73
50
215
354
109
23
17
216
3
73
50
215
354
109
23
17
216
4
73
50
17
354
109
23
215
216
5
73
50
17
354
109
23
215
216
6
73
50
17
23
109
354
215
216
7
73
50
17
23
109
354
215
216
8
73
50
17
23
109
354
215
216
9
73
50
17
23
109
354
215
216
10
73
50
17
23
109
354
215
216
11
17
50
73
23
109
354
215
216
12
17
50
73
23
109
354
215
216
13
17
50
73
23
109
354
215
216
14
17
50
23
73
109
354
215
216
15
17
50
23
73
109
354
215
216
16
17
50
23
73
109
354
215
216
17
17
23
50
73
109
354
215
216
18
17
23
50
73
109
354
215
216
19
17
23
50
73
109
354
215
216
20
17
23
50
73
109
215
354
216
21
17
23
50
73
109
215
354
216
22
17
23
50
73
109
215
354
216
23
17
23
50
73
109
215
216
354


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


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
146

81
146
152
270
301
321
330
2
146

81
146
152
270
301
321
330
3
146

81
146
152
270
301
321
330


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
41

41
64
77
83
109
120
156
168
189
193
243
272
289
2
41

41
64
77
83
109
120
156
168
189
193
243
272
289
3
41

41
64
77
83
109
120
156
168
189
193
243
272
289
4
41

41
64
77
83
109
120
156
168
189
193
243
272
289


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!