Exploring Sorting Algorithms in Computer Science

CS 132, Winter 2024 Lecture 37: sorting Thank you to Marty Stepp and Stuart Reges for parts of these slides

Binary search binary search: Locates a target value in a sorted array or vector by successively eliminating half of the vector from consideration. How many elements will it need to examine? Example: Searching the vector below for the value 42: index value -4 0 1 2 2 7 3 10 15 20 22 25 30 36 42 50 56 68 85 92 103 4 5 6 7 8 9 10 11 12 13 14 15 16 min mid ma x 2

Requirements What types can our binarySearch function be called on? Any type? Requirements? operator < operator > 3

Sorting sorting: Rearranging the values in a collection into a specific order. can be solved in many ways: Algorithm Description bogo sort shuffle and pray bubble sort swap adjacent pairs that are out of order selection sort look for the smallest element, move to front insertion sort build an increasingly large sorted front portion merge sort recursively divide the data in half and sort it shell sort sort every k th element for decreasing values of k heap sort place the values into a binary heap then dequeue quick sort recursively "partition" data based on a pivot value bucket sort cluster elements into smaller groups, sort the groups radix sort sort integers by last digit, then 2nd to last, then ... 4

Sorting sorting: Rearranging the values in a collection into a specific order. can be solved in many ways: Algorithm Description bogo sort shuffle and pray bubble sort swap adjacent pairs that are out of order selection sort look for the smallest element, move to front insertion sort build an increasingly large sorted front portion merge sort recursively divide the data in half and sort it shell sort sort every k th element for decreasing values of k heap sort place the values into a binary heap then dequeue quick sort recursively "partition" data based on a pivot value bucket sort cluster elements into smaller groups, sort the groups radix sort sort integers by last digit, then 2nd to last, then ... 5

Bogo sort bogo sort: Orders a list of values by repetitively shuffling them and checking if they are sorted. name comes from the word "bogus"; a.k.a. "bogus sort" The algorithm: Scan the list, seeing if it is sorted. If so, stop. Else, shuffle the values in the list and repeat. This sorting algorithm (obviously) has terrible performance! What is its runtime? 6

Bogo sort code // Places the elements of v into sorted order. void bogoSort(vector<int>& v) { while (!isSorted(v)) { shuffle(v.begin(), v.end(), default_random_engine(seed)); // from shuffle.h } } // Returns true if v's elements are in sorted order. bool isSorted(vector<int>& v) { for (int i = 0; i < v.size() - 1; i++) { if (v[i] > v[i + 1]) { return false; } } return true; } 7

Bogo sort runtime How long should we expect bogo sort to take? related to probability of shuffling into sorted order assuming shuffling code is fair, probability equals 1 / (number of permutations of N elements) N= PN ! N average case performance: O(N * N!) worst case performance: O( ) What is the best case performance? 8

Selection sort selection sort: Orders a list of values by repeatedly putting the smallest or largest unplaced value into its final position. The algorithm: Look through the list to find the smallest value. Swap it so that it is at index 0. Look through the list to find the second-smallest value. Swap it so that it is at index 1. ... Repeat until all values are in their proper places. 9

Selection sort example Initial array: index 0 value 22 18 12 -4 1 2 3 4 27 30 36 50 5 6 7 8 7 9 68 91 56 10 11 12 13 14 15 16 2 85 42 98 25 After 1st, 2nd, and 3rd passes: index value -4 18 12 22 27 30 36 50 0 1 2 3 4 5 6 7 8 7 9 68 91 56 10 11 12 13 14 15 16 2 85 42 98 25 index value -4 0 1 2 2 12 22 27 30 36 50 3 4 5 6 7 8 7 9 68 91 56 18 85 42 98 25 10 11 12 13 14 15 16 index value -4 0 1 2 2 7 3 4 5 6 7 8 9 10 11 12 13 14 15 16 22 27 30 36 50 12 68 91 56 18 85 42 98 25 10

Selection sort example selection sort: Repeatedly swap smallest unplaced value to front. 2 -1 -4 12 8 11 11

Selection sort code // Rearranges elements of v into sorted order. void selectionSort(vector<int>& v) { for (int i = 0; i < v.size() - 1; i++) { // find index of smallest remaining value int min = i; for (int j = i + 1; j < v.size(); j++) { if (v[j] < v[min]) { min = j; } } // swap smallest value to proper place, v[i] if (i != min) { int temp = v[i]; v[i] = v[min]; v[min] = temp; } } } 12

Selection sort runtime What is the complexity class (Big-Oh) of selection sort? O(N2). 13

Selection sort example selection sort: Repeatedly swap smallest unplaced value to front. index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 value 22 18 12 -4 27 30 36 50 7 68 91 56 2 85 42 98 25 n n 14

Insertion Sort insertion sort: orders a list of values by repetitively inserting a particular value into a sorted subset of the list index 0 1 2 3 4 5 6 7 value 15 2 8 1 17 10 12 5 pass 1 2 15 8 1 17 10 12 5 pass 2 2 8 15 1 17 10 12 5 pass 3 1 2 8 15 17 10 12 5 pass 4 1 2 8 15 17 10 12 5 pass 5 1 2 8 10 15 17 12 5 pass 6 1 2 8 10 12 15 17 5 pass 7 1 2 5 8 10 12 15 17 15

Insertion sort example Makes N-1 passes over the array. At the end of pass i, the elements that occupied A[0] A[i] originally are still in those spots and in sorted order. 2 8 1 17 10 12 5 15 16

Insertion sort code // Rearranges the elements of v into sorted order. void insertionSort(vector<int>& v) { for (int i = 1; i < v.size(); i++) { int temp = v[i]; // slide elements right to make room for v[i] int j = i; while (j >= 1 && v[j - 1] > temp) { v[j] = v[j - 1]; j--; } v[j] = temp; } } 17

Merge sort merge sort: Repeatedly divides the data in half, sorts each half, and combines the sorted halves into a sorted whole. The algorithm: Divide the list into two roughly equal halves. Sort the left half. Sort the right half. Merge the two sorted halves into one sorted list. Often implemented recursively. An example of a "divide and conquer" algorithm. Invented by John von Neumann in 1945 Runtime: O(N log N). Somewhat faster for asc/descending input. 18

Merge sort example index 0 1 2 3 4 5 6 7 value 22 18 12 -4 58 split 7 31 42 22 18 12 -4 58 7 31 42 split split 22 18 12 -4 58 7 31 42 split split split split 22 18 12 -4 58 7 31 42 merge merge merge merge 18 22 -4 12 7 58 31 42 merge merge -4 12 18 22 7 31 42 58 merge -4 7 12 18 22 31 42 58 19

Merging sorted halves 20

Merge sort code // Rearranges the elements of v into sorted order using // the merge sort algorithm. void mergeSort(vector<int>& v) { if (v.size() >= 2) { // split vector into two halves vector<int> left; for (int i = 0; i < v.size()/2; i++) {left += v[i];} vector<int> right; for (int i = v.size()/2; i < v.size(); i++) {right += v[i];} // recursively sort the two halves mergeSort(left); mergeSort(right); // merge the sorted halves into a sorted whole v.clear(); merge(v, left, right); } } 21

Merge halves code // Merges the left/right elements into a sorted result. // Precondition: left/right are sorted void merge(vector<int>& result, vector<int>& left, vector<int>& right) { int i1 = 0; // index into left side int i2 = 0; // index into right side for (int i = 0; i < left.size() + right.size(); i++) { if (i2 >= right.size() || (i1 < left.size() && left[i1] <= right[i2])) { result += left[i1]; // take from left i1++; } else { result += right[i2]; // take from right i2++; } } } 22

Merge sort runtime What is the complexity class (Big-Oh) of merge sort? O(N log N). 23

More runtime intuition Merge sort performs O(N) operations on each level. Each level splits the data in 2, so there are log2N levels. (height) Product of these = N * log2N = O(N log N). Example: N = 32. Performs ~ log2 32 = 5 levels of N operations each: (width) (area) 32 16 height = log2 N 8 4 2 1 width = N 24

Built in functions in C++ STL The algorithm header contains many useful built in functions including binary_search, sort and stable_sort bool test(Critter* a, Critter* b) { int aX = a.getX(); int bX = b.getX(); int aY = a.getY(); int bY = b.getY(); return aX < bX || (aX == bX && aY < bY); } vector<string> words{"foo", "bar", "baz", "ball"}; sort(words.begin(), words.end()); cout << words << endl; // {ball, bar, baz, foo} // positions: (20, 14) (20, 2) (4, 47) vector<Critter*> critters {new Ant(true), new Hippo(5), new Cat()}; sort(critters.begin(), critters.end(), test); cout << critters << endl; // {Cat, Hippo, Ant} 25

Stable sorting stable sort: One that maintains relative order of "equal" elements. important for secondary sorting, e.g. sort by name, then sort again by age, then by salary, ... All of the N2 sorts shown are stable bubble, selection, insertion Merge sort is stable. Quick sort is not stable. The partitioning algorithm can reverse the order of "equal" elements. 26

Unstable sort example Suppose you want to sort these points by Y first, then by X: [(4, 2), (5, 7), (3, 7), (3, 1)] A stable sort like merge sort would do it this way: [(3, 1), (4, 2), (5, 7), (3, 7)] sort by y [(3, 1), (3, 7), (4, 2), (5, 7)] sort by x Note that the relative order of (3, 1) and (3, 7) is maintained. Quick sort might leave them in the following state: [(3, 1), (4, 2), (5, 7), (3, 7)] sort by y [(3, 7), (3, 1), (4, 2), (5, 7)] sort by x Note that the relative order of (3, 1) and (3, 7) has reversed. 27

In-place sorting In-place: not needing to copy the array/vector, just needing space for constant sized variables Which of the sorts that we have seen so far can we do in- place? selection sort insertion sort bubble sort quick sort (usually considered in place even though variable space is needed for stack pointers to recursive calls) 28

Sorting in the real world What sort does STL's sort use? a hybrid of multiple sorts Insertion sort Quick sort Heap sort Most real-world sorts are hybrids as the setup cost for the more efficient sorts is really high when the amount of data is small. If you are asked to implement a sort in an interview I would generally recommend going for merge sort efficient, good sort that is commonly used stable much easier to get right in an interview than quick sort 29