Week 11/12: Sorting Efficiency

It started in CSC108 with Bubble Sort. A rather simple algorithm that takes a list at index i and j = i + 1. If list[i] > list[j], i is switched with j.Then compare list[i + 1] and list[j + 1]. Very similarly, we have Selection Sort, which instead makes one exchange on the largest number in the unsorted part of the list for every pass through. These are O(n^2).

Insertion Sort is O(n^2), but it keeps the sorted part at the beginning of the list. It assumes that the first number is sorted (which it is, because one number is always sorted). The next number is checked against the sorted list starting at the right, and inserted to the left once it is less than the number it is being checked against.

Then we get to CSC148 and get hard-to-read algorithms like Merge Sort and Quick Sort. Merge Sort and Quick Sort both deal recursively with lists. Merge Sort takes a list and divides it by two and then divides those by two until it has length 1 lists. They are then pieced back together. Whenever two lists are compared, they are compared at index 0. So, if one list is completely read before the other, the other can just be appended to the end of the new one because it is sorted and its number at index 0 > all the numbers in the other half of the list. Quick Sort takes a pivot point (usually random to get an average runtime of O(nlogn) and a worst case of O(n^2)). This involves a leftmark and rightmark. They are moved toward each other, sorting on the way, and once they pass each other, a split point is found. Then it recursively quick sorts the left half and right half based on the split point.

Overall, large lists become too much to handle for the first 3 sorting methods, despite Quick Sort being unstable at times.