Sorting and efficiency

This week we're supposed to do a post about sorting algorithms and their efficiency. Last semester in CSC108 we learned about some sorting algorithms like bubble sort, insertion sort and so on, but we didn't focus much on what makes them unique in terms of efficiency. For the purposes of this entry I'll be focusing on three specific sorting algorithms, selection sort, merge sort and quick sort.

Before I get in to it, lets discuss efficiency of algorithms. When we're talking about the efficiency of algorithms we use Big O notation. We write it like this O(x) where x represents whatever argument describes the algorithm's efficiency. For example, if we're given a list of size n, and an algorithm that checks each value in the list once, in general it would mean the algorithm's efficiency is O(n). If an algorithm compares each value in the list against every other value in the list, we would have an algorithm with efficiency O(n^2). This is a simple way of looking at it, but I hope it illustrates the point. Now to the algorithms!

We'll start with Selection Sort. I chose to look at selection sort first because it's one of the most basic sorting algorithms. Unfortunately it also happens to be one of the more inefficient algorithms that we use. What does selection sort do? Well, given an unordered list, we find the lowest element in the list and then place it in the beginning of the new list. Now repeat on all the remaining elements (a list of length n - 1). Eventually this will give you an ordered list. Sounds pretty simple and intuitive right? Well it is, but in order to find the lowest element in a list, we have to compare a given value against every other value in the list. As we said above (when discussing efficiency of algorithms), this would require n^2 separate checks, thus giving us an efficiency of O(n^2) for Selection Sort.

Lets move on to Merge Sort. This sorting algorithm is actually pretty cool, but harder to grasp then selection sort. Given a list, we divide the list up until we have sublists each consisting of one element. Now we compare the first element of each list (at the start it's just one) and append the smaller element to a new list (note, we could also append the larger, we just have to be consistent). Now we will have n/2 sublists of 2 elements. We repeat by merging these new sublists by comparing the first element of each list and appending the smaller one to a new list. Eventually we will have a merged and ordered list of the initial n elements. This algorithm generally takes lgn splits to split up a list of n elements, and n elements will be inspected lgn times (once for each split when merging). Although the efficiency is more like lgn + nlgn, we drop the smaller term when describing big O efficiency and are left with O(nlgn) efficiency for Merge Sort.

Finally lets discuss Quick Sort. The way it works is given an unordered list, the first element is taken, and used as a partition. Then every element in the list that is smaller than this element is put into one list, while everything larger is put into another list. We then repeat this process on the sublists until eventually (once we combine all these sublists from smallest to largest) we end up with a sorted list. Since this algorithm has n comparisons per split, this algorithm like merge sort has O(nlgn) efficiency...In the best case scenario. The risk with Quick Sort is that in the worst case, the split points may not be anywhere close to the middle of the list, and in fact could be all the way to the left or the right, resulting in incredibly uneven divisions. The result of this scenario is an algorithm with O(n^2) efficiency.