Sorting Algorithm and their Efficiency

    This week’s final (?) slog is about Sorting Algorithms and their efficiency, which is like a combination of the things I learnt in CSC108 (Sorting Algorithms) and CSC165 (their Efficiency or time complexity). 


    Sorting is the process of analyzing and then organizing a collection of data (for example, lists) in a particular order. There are many different types of sorting algorithms, and they are bubble sort, insertion sort, merge sort, quick sort, selection sort and Python’s built-in sort, ‘Timsort’, which is a combination of merge sort and insertion sort. I will now briefly talk about each algorithm.

    Bubble sort, basically, runs through each element in the input and switches the element if it is ‘out of order’. Obviously, it is not a good idea to use bubble sort on large inputs. Insertion sort partitions the input into 2 regions (sorted and unsorted); it checks each element in the unsorted region and inserts it into the correct position in the sorted region. The algorithm for insertion sort has two nested loops – one for the unsorted region and the other inner loop for the sorted region in finding the position where the element should be ‘placed’. Additionally, there’s selection sort, which goes through each element and swaps the element with the smallest element in the input array or list. Similarly, there are two loops for selection sort: a for loop for each element in the input and another for finding the smallest element in the rest of the input list. Thus, these algorithms have runtime of O(n^2).

    Next, we have merge sort, which splits the input data or list into 2 equal halves and continuously splits each half until a single element is in either half, which then sorts the ‘halved’ sections and finally merge the two halves until the entire list is formed. Clearly, this algorithm calls itself recursively. Similarly, quick sort also recursively splits the input data into 2 (possibly, unequal) halves about a ‘pivot’ element in the list, where the half to the left of the pivot contains the elements that are less than the pivot element, while the other half (to the right) contain the elements larger than the pivot.

    In CSC165, we used upper, lower and tight bounds to describe the time complexity and efficiency of various algorithms. The ‘in-depth’ analysis of algorithms taught in CSC165 has helped me in analyzing the time complexity for CSC148. We use the upper bound of runtimes, using the Big-Oh notation, which eliminates constant factors, to give us a measure of an algorithm’s efficiency. Worst case runtimes are, just as the name says, the most (or worst) time an algorithm will take to perform. Anyway, in the lectures and lab sessions, we analyzed the efficiency of various sorting algorithms. We found that merge sort and quick sort both had O(n log n) runtimes, which uses the ‘divide-and-conquer’ technique, whereas bubble, insertion and selection sort all had O(n^2) worst-case runtime, which is worse than the logarithmic runtime. Thus, merge sort and quick sort were found to be more efficient compared to the latter 3 sorting algorithms. On the side note, a runtime of O(1), simply means that the runtime is independent of the size of input, and O(n) means that the runtime grows linearly with the input size. The order of runtimes from best to worst is as follows:  O(1) < O(log n) < O(n) < O(n log(n)) < O(n^2)

    I found that algorithms with logarithmic runtimes were the most difficult to understand because at first, I didn’t get how one can tell if something is logarithmic, and in addition to that, I found it really complicated to analyze the ‘divide and conquer’ methods; not that it is difficult, it is just a bit too complex for me to keep track of, due to the recursive division of the input’s data. Because of this, I didn’t quite get the last two questions of the CSC148 mid-term Test 2, which was about algorithm’s time complexity. Therefore, I hope to spend more time practicing my algorithm analysis for both CSC148 and CSC165 before the final exam! Well, I hope this post helped by giving a quick and brief explanation of sorting algorithms and their efficiency (sorry for its length) and farewell!! J