Sorting algorithms is another broad subject. Really, all a sorting algorithm is is a particular method of arranging a number of items into a particular order. For the sake of the course, we typically sort lists integers into ascending order. 148 focuses on a few sorting algorithms in particular: Insertion Sort, Selection sort, Quicksort, Merge sort, and bubble sort.
-Insertion sort works by creating an already sorted sublist at the front of a list, and loops through the unsorted values, adding them to the correct place in the sorted section. The worst case complexity of insertion sort is n^2, and the best case is n.
-Merge sort works by splitting the entire list of integers into individual sublists, then merges pairs of numbers randomly into sorted sublists of two items. It then repeats that process on the larger sublists, merging until there is only one list left. The best and worst case performance is nlogn.
-Quicksort works by first picking a pivot point anywhere in the list. It then swaps elements larger than the value of the pivot point to the right of the pivot, and items smaller than it to the left. Then, it picks two new pivots, one on each side of the original pivot, and recursively sorts each side of the pivot, until there are no more values on either side of the pivot to sort. The worst case performance is n^2, and the best case is nlogn.
-Selection sort works by finding the minimum value of the list, and moving it to the front of the list. That section is then designated sorted, and then it repeats, finding the minimum value of everything past the sorted section, and moving it to the bottom of the sorted section, until it reaches the end of the list. Selection sort always runs at n^2 complexity.
-Bubble sort works by 'bubbling up' larger values in the list. It looks at the first value of the list, then, if it is larger than the value to the right of it, it is swapped up one index. The comparison and swapping is done until a value is found that is larger than the value being bubbled up, then the swapping stops and the algorithm looks back to the front of the list. When the first values are in order, it looks to the pair of values to the right, and swaps them if they are awry. If it reaches the end of the list without swapping, the list is sorted. Bubble sort has a best case performance of n, and a worst case performance of n^2.
That's a quick overview of all the algorithms we've made from scratch in 148. However, this ignores an algorithm that we've used, but not programmed. It's worth mentioning python's builtin sorting algorithm, which is Timsort. Unfortunately, I don't really know how timsort works.
