Sorting Algorithms

Much of the coursework in the passed few weeks has been centred around sorting algorithms. I was really looking forward to studying these! Professor Heap gave great demonstrations of implementations of select sort, merge sort, and quick with his different-sized empty coffee cups; these demonstrations helped make the algorithms more concrete and memorable. We then went on to discuss the efficiency of the different sorting algorithms which was very interesting. Selection sort was the least efficient out of the three: it has O(n^2) efficiency. Merge sort on the other hand is much more efficient and has O(nlogn) efficiency, while quicksort has O(nlogn) efficiency in the best case scenario and, contrary to its name, O(n^2) efficiency in the worst case! This inefficiency in the worst case scenario arises because of the choice of a pivot element. The pivot element is used to split the list in two parts: on part containing elements less than the pivot and the other part containing elements greater than the pivot. Then the algorithm is performed recursively on the two parts and so on and so forth until one element or empty parts are obtained, which are of course already sorted. Then the list is put back together again in already sorted order. Ideally, the pivot element is somewhere close to the median of the list, but it is possible (albeit unlikely) that the pivot is repeatedly at the lower end or the upper end of the list, in which case the benefit of dividing and conquering is lost and the algorithm becomes similar to select sort. In our implementation of the algorithm we chose the pivot from first element of the list in each step, but we spoke about how the code could be modified to pick the pivot from a random index, which in the case of an already sorted or nearly-sorted list would help to avoid the worst case scenario. Merge sort, despite being a divide-and-conquer algorithm doesn't have this same problem because when the list is split in each step, it is done by simply splitting it into two halves. One thing that really surprised me was how few steps it takes to split a list into single element or empty parts by repeatedly splitting the list in two; the power of exponential growth is always surprising! When it comes to coding the algorithms, I much prefer the code for quicksort because it doesn't involve any complicated merging procedure as is necessary in merge sort. However, these aren't the only sorting algorithms that we have been studying. In our labs we also looked at bubble sort which is a simple but not very efficient sorting algorithm: it typically has O(n^2) (in)efficiency, but if an already sorted list is passed to it, it has O(n) efficiency. So bubble sort is slightly better than selection sort. It has O(n) efficiency for an already sorted list because the algorithm involves going through each item of the list in sequence in each step of the algorithm and if the list is already sorted it simply returns it on the first step. There is a plethora of different sorting algorithms and at first even the few that we studied seemed like a lot. Wikipedia has a great article on sorting algorithms with a comparison chart of the algorithms' big-O efficiencies. Each sorting algorithm also has its own article and some of them have very elucidating animations that demonstrate the sorting algorithms with a large list. I found wikipedia to be a very useful resource and I suggest you check it out if you haven't done so already!