Sorting and efficiency analysis

        Hey, this is the last week of CSC148 and it’s nice to be back here and write down some final thoughts on sorting and efficiency over the last week.

        I am going to start this slog with a slight digression here. http://www.sorting-algorithms.com/ is a quite intriguing website where you could view the animation of different sorting algorithms and with the help of this animation, I will start talking about run-time complexity of different algorithms learned in the last two weeks.

        First of all, what is run-time complexity? Basically, run-time complexity features the growth rate of the total steps the algorithm would take as the size of input increases and we use big-Oh(O) to describe the asymptotic behavior the algorithm( check my previous slog http://siyangcsc148w3.blogspot.ca/2014/03/introduction-to-runtime-complexity.html for more information on big-Oh and how to quickly determine the run-time complexity of a procedural algorithm and http://siyangcsc148w3.blogspot.ca/2014/03/hi-its-nice-to-be-back.html for information on how to determine big-Oh of the recursive algorithm).  Since computers can’t run infinitely fast, there’s a need to come up with algorithms that can take fewer steps to address the same problem and here run-time complexity analysis will play a major role in determining whether the algorithm is more efficient or not.

        As you become more familiar with analyzing run-time complexity of algorithms, I can now start the analysis of sorting algorithm which becomes increasingly vital in recent years due to big data computation. I’ll begin with the procedural sorting algorithm we learnt – selection sort

Selection sort is the sorting algorithm that starts sorting from the beginning of a list by finding out the smallest element of the rest of list and exchange the smallest element with the element at the very beginning. Them the algorithm does the same thing for the list without the first element, without the first two elements…… until it reaches the last element of the list. We could verify this algorithm actually works by proving the loop invariant that the first i-th element are sorted after the i-th iteration of the loop shown in the picture using induction. I’m not going to spend time on the correctness of the algorithm as it’s beyond the scope of CSC148 but focus on analyzing its run-time complexity. Since this algorithm is a procedural algorithm, you can use the trick I mentioned in http://siyangcsc148w3.blogspot.ca/2014/03/introduction-to-runtime-complexity.html by counting the depth of loops that depend on the size of input. There is one loop that is quite obvious here – ‘ for I in range(len(L1)):’ and the time it will iterate depends on the length of the input – so it is at least O(n), but there is actually a loop hidden inside ‘min(L1([i:]))’ where every element in L1[i:] is compared with each other to determine the smallest element of L1[i:] and exchange it with L1[i]. Since the loop over L1[i:] also depends  on the length of L1, I can guess that run-time complexity for selection sort is O(n^2). And we can easily prove my guess by analyzing the steps take for each inner loop and outer loop. Notice here we only count the number of comparisons into total steps for simplicity. So for the inner loop where the algorithm finding out the smallest element of L1[i:], it would take n-i comparisons for each iteration and since the outer loop iterates n times ( n is the length of L1) with i incremented by 1 after each iteration, so the total number of comparisons for L1 with size n  is approximately n+(n-1)+(n-2)+……+1 = n(n+1)/2 which by the definition of big-Oh, belongs to O(n^2). Same strategy applies to both bubble sort – which continuously ‘bubbles’ the biggest element to the end of the list by comparing each element with the one next to it and insertion sort – which insert the element into an already sorted list. And they all have run-time complexity O(n^2). Notice that in the animation I mentioned above, bubble sort seems to be much more inefficient than insertion and selection sort, it still belongs to O(n^2) as we only care about the asymptotic behavior.

Then comes to the recursive sorting algorithm. I’m elaborate quick sort here instead of merge sort ( You can check http://siyangcsc148w3.blogspot.ca/2014/03/hi-its-nice-to-be-back.html for merge sort analysis through master theorem and telescoping). Let’s first take a look at quick sort –

 Quick sort uses recursion by picking a pivot(here we pick the first element of the list as the pivot) and divide the list into two parts where one part contains elements smaller than the pivot and the other part contains elements larger than the pivot and apply quick sort to these two parts using recursion and the pivot in between. Analyzing this algorithm, unlike mergesort which does not have best case and worse case, turns out to be much trickier. Let’s consider the a balanced list where half of the element is less than the first element while the other half is larger than the first element. It turns out we will split the list into half after each call and at the end, we need to combine these elements together by making copies of the list sorted which takes O(n) complexity. It’s kind of similar to merge sort in the slog I mentioned earlier and it’s quite obvious the run-time complexity for quick sort is O(nlogn) for a balanced list. However, what if the list is already sorted, it turns every call only splits the list into the pivot and a list of all other elements which takes n calls to reach the base case so its run-time complexity is O(n^2) and this is the worst case for quick sort. O(n^2) as we all know is not efficient at all so we must find out a way to resolve this problem. It turns out by randomly select a pivot or select the middle of the list as pivot could bring the worst case run-time complexity down to O(nlogn) as the list will become more balanced when dividing.

        So I’ve talked about both procedural sorting algorithm and recursive algorithm, here I would like to make a brief summary of how to quickly find out the run-time complexity – For procedural algorithms, as I’ve talked about before, it’s more associated with the depth of nested loop which depends on the size of input while for recursive sorting algorithms, it’s more associated with the number of dividing that leads to the base case and the steps needed for processing the result of smaller cases. Below is a chart of the time complexity of the algorithms we’ve talked about

Notice quick sort is O(nlogn) only when the pivot is picked randomly or in the middle. Count sort only deal with lists that contain elements of value less than the length of the list.

So this is the end of my slog. Thanks for reading. Also, thanks to the TA who grades my slog.