diff options
Diffstat (limited to '06-01.md')
| -rw-r--r-- | 06-01.md | 266 |
1 files changed, 266 insertions, 0 deletions
diff --git a/06-01.md b/06-01.md new file mode 100644 index 0000000..9a814b6 --- /dev/null +++ b/06-01.md @@ -0,0 +1,266 @@ +[\<- 05/29](05-29.md) + +--- + +## Sorting + +- Different ways to classify sorting algorithms + - **Internal** + - All data to be sorted is in memory + - **External** + - the data is kept on disk and small pieces of data are brought into memory to be processed + - For example, a file of 20,000 records may be sorted using an array that holds only 1000 records. During the sorting process, only 1000 records are in memory at any one time + +- Another way to classify sorting algorithms: + - **Stable**: if two records to be sorted, r1 and r2 have identical sort keys, and if r1 comes before r2 in the original input, then r1 comes before r2 in the sorted output + - **Unstable**: the order of the records with identical keys is not guaranteed + - Example: + - sort students according to their age. student A - 20 and student B - 20 (don't want subsequent sort to mess up previous sort) + +- Yet another way to classify sorting algorithms (based on how they work): + - **Selection-based**: repeatedly select the smallest (or largest) remaining item and place it in the output + - e.g., selection sort, heap sort + - **Insertion-based**: you take the next available item and insert it in its proper place in a sorted list + - e.g., insertion sort, shell sort, tree sort + - **Exchange-based**: intelligently exchange or swap two items in the list until the list is sorted + - e.g., bubble sort, quick sort + - **other**: doesn't fit into any of the above categories + - e.g., radix sort, merge sort (sometimes called "sortless sort" algorithms) + +# Sorting Algorithms + +- We're starting with the easiest algorithm in each category first + - **Selection-based**: selection sort + - **Insertion-based**: insertion sort + - **Exchange-based**: bubble sort +- Note that, like with data structures, there is no one ideal sorting algorithm + +## Selection Sort + +- How it works? + - the array is logically partitioned into two sections: sorted and unsorted + - the sorted section is also in the correct location + - repeatedly find the next smallest item from the unsorted section and then move it into its correct position + +### One Sort Pass + +- One sort pass: each time an element moves from the unsorted sublist to the sorted sublist +- Ex. sort 44, 10, 21, 78, 53, 92, 37, 85 + +|Unsorted|Unsorted|Unsorted|Unsorted|Unsorted|Unsorted|Unsorted|Unsorted| +|--------|--------|--------|--------|--------|--------|--------|--------| +|44 |10 |21 |78 |53 |92 |37 |85 | + +- Swap 10 and 44 + +|Sorted |Unsorted|Unsorted|Unsorted|Unsorted|Unsorted|Unsorted|Unsorted| +|--------|--------|--------|--------|--------|--------|--------|--------| +|10 |44 |21 |78 |53 |92 |37 |85 | + +- Swap 44 and 21 + +|Sorted |Sorted |Unsorted|Unsorted|Unsorted|Unsorted|Unsorted|Unsorted| +|--------|--------|--------|--------|--------|--------|--------|--------| +|10 |21 |44 |78 |53 |92 |37 |85 | + +- Swap 44 and 37 + +|Sorted |Sorted |Sorted |Unsorted|Unsorted|Unsorted|Unsorted|Unsorted| +|--------|--------|--------|--------|--------|--------|--------|--------| +|10 |21 |37 |78 |53 |92 |44 |85 | + +- Swap 78 and 44 + +|Sorted |Sorted |Sorted |Sorted |Unsorted|Unsorted|Unsorted|Unsorted| +|--------|--------|--------|--------|--------|--------|--------|--------| +|10 |21 |37 |44 |53 |92 |78 |85 | + +- 53 is already in the right place, so it would just swap with itself + +|Sorted |Sorted |Sorted |Sorted |Sorted |Unsorted|Unsorted|Unsorted| +|--------|--------|--------|--------|--------|--------|--------|--------| +|10 |21 |37 |44 |53 |92 |78 |85 | + +- Swap 92 and 78 + +|Sorted |Sorted |Sorted |Sorted |Sorted |Sorted |Unsorted|Unsorted| +|--------|--------|--------|--------|--------|--------|--------|--------| +|10 |21 |37 |44 |53 |78 |92 |85 | + +- Swap 92 and 85 + +|Sorted |Sorted |Sorted |Sorted |Sorted |Sorted |Sorted |Sorted | +|--------|--------|--------|--------|--------|--------|--------|--------| +|10 |21 |37 |44 |53 |78 |85 |92 | + +- The array is sorted! + +``` +void selectionSort(int a[], int n){ + int i, j, min, temp; + + for(i=0; i<n-1; i++){ + min = i; //slot of smallest value + for(j=i+1; j<n; j++){ + if(a[j] < a[min]) min = j; + } + //swap + temp = a[i]; + a[i] = a[min]; + a[min] = temp; + } +} +``` + +- Big-O runtime: O(n^2) +- Stable? Unstable? + - Ex. 4 2 3 4 1 + - Algorithm is unstable +- What is the space overhead? (the what?) + - How much extra space is needed by our algorithm? + - We sort the array in place + - All we need is a few integers, so the overhead is O(1) + +### Can we make it stable? + +- Selection sort can be made stable by shifting rather than swapping +- This change is typically not made, because as we coded it, selection sort does the fewest number of memory writes of any sorting algorithm + +## Insertion Sort + +- Card players: Each time they pick up a card, **insert it into the proper sequence** in their hand +- How it works? take the next item in the array and place it in an already sorted list of items + - In this case, the sorted partition will not necessarily in the proper final position + +- ex. Sort 44, 10, 21, 78, 53, 92, 37, 85 + +|Sorted |Unsorted|Unsorted|Unsorted|Unsorted|Unsorted|Unsorted|Unsorted| +|--------|--------|--------|--------|--------|--------|--------|--------| +|44 |10 |21 |78 |53 |92 |37 |85 | + +- 10 should be inserted before 44 + +|Sorted |Sorted |Unsorted|Unsorted|Unsorted|Unsorted|Unsorted|Unsorted| +|--------|--------|--------|--------|--------|--------|--------|--------| +|10 |44 |21 |78 |53 |92 |37 |85 | + +- 21 should be inserted between 10 and 44 + +|Sorted |Sorted |Sorted |Unsorted|Unsorted|Unsorted|Unsorted|Unsorted| +|--------|--------|--------|--------|--------|--------|--------|--------| +|10 |21 |44 |78 |53 |92 |37 |85 | + +- 78 is already sorted + +|Sorted |Sorted |Sorted |Sorted |Unsorted|Unsorted|Unsorted|Unsorted| +|--------|--------|--------|--------|--------|--------|--------|--------| +|10 |21 |44 |78 |53 |92 |37 |85 | + +- 53 should be inserted between 44 and 78 + +|Sorted |Sorted |Sorted |Sorted |Sorted |Unsorted|Unsorted|Unsorted| +|--------|--------|--------|--------|--------|--------|--------|--------| +|10 |21 |44 |53 |78 |92 |37 |85 | + +- 92 is already sorted + +|Sorted |Sorted |Sorted |Sorted |Sorted |Sorted |Unsorted|Unsorted| +|--------|--------|--------|--------|--------|--------|--------|--------| +|10 |21 |44 |53 |78 |92 |37 |85 | + +- 37 should be inserted between 21 and 44 + +|Sorted |Sorted |Sorted |Sorted |Sorted |Sorted |Sorted |Unsorted| +|--------|--------|--------|--------|--------|--------|--------|--------| +|10 |21 |37 |44 |53 |78 |92 |85 | + +- 85 should be inserted between 78 and 92 + +|Sorted |Sorted |Sorted |Sorted |Sorted |Sorted |Sorted |Sorted | +|--------|--------|--------|--------|--------|--------|--------|--------| +|10 |21 |37 |44 |53 |78 |85 |92 | + +- The Array is Sorted! + +``` +void insertionSort(int a[], int n){ + int i, j, temp; + + for(i=1; i<n; i++){ + temp = a[i]; + for(j=i-1; j>=0 && temp>a[i]; j--){ + a[j+1] = a[j]; + } + a[j+1] = temp; + } +} +``` + +- Big-O Runtime: + - Worst Case: O(n^2) + - Best Case: O(n) (When the array is already sorted) + - Average: O(n^2) + +- Stable? Unstable? + - Stable: the loop uses a `<` instead of `<=` +- Space overhead? + - Again, we sort the array in place + - All we need are a few integers, so O(1) overhead + +## Exchange Sort + +- Concept: exchange elements that are out of order until the entire list is sorted +- Feature: use exchange extensively + +## Bubble Sort + +- What is bubble sort: + - The list at any moment is divided into two sublist: sorted and unsorted + - The smallest element is bubbled from the unsorted sublist and moved to the sorted sublist + - After moving the smallest to the sorted list the wall moves one element to the right, increasing the number of sorted elements and decreasing the number of unsorted ones + +- Ex. sort 44, 10, 21, 78, 53, 92, 37, 85 + - Comapre 85 and 37: correct order + - Compare 37 and 92: they should be swapped + - 44, 10, 21, 78, 53, 37, 92, 85 + - Compare 37 and 53: they should be swapped + - 44, 10, 21, 78, 37, 53, 92, 85 + - Compare 37 and 78: they should be swapped + - 44, 10, 21, 37, 78, 53, 92, 85 + - Compare 37 and 32: correct order + - Compare 21 and 10: correct order + - Compare 10 and 44: they should be swapped + - 10, 44, 21, 37, 78, 53, 92, 85 + - This is the array after the first pass + - Only one item is in the right place (10) + - Continue to do passes until the entire array is sorted + +``` +bool sorted = false; //flag to avoid unneccessary looping +for(i = 0; i < (n-1) && !sorted; i++){ + sorted = true; + for(j = n-1; j>i; j--){ //don't go over elements already in position + if(a[j] < a[j-1]){ + temp = a[j]; + a[j] = a[j-1]; + a[j-1] = temp; + sorted = false; + } + } +} +``` + +- What's the best-case big-O? O(n) (if we use the sorted flag +- Worst Case? O(n^2) +- Average? O(n^2) + +- Is it stable? + - Yes: only swap if `<` rather than `<=` + +- Space overhead? O(1) +- Statistically, this looks just as good as insertion sort, but it involves much more writing, so it is slower in actuality + +## Check Out These Sorting Algorithm Visualizations + +- [sorting.at](http://sorting.at) +- [cs.usfca.edu/~galles/visualization/ComparisonSort.html](https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html) |