Week11

    Sorting & Efficiency.

     To talk about sorting and efficiency problem, let's go back to CSC108 first. In CSC108, we learnt three simple sorting techniques, which are bubble sort, selection sort, and insertion sort. Although they are implemented in different ways, they achieve quite similar performances. In the worst case, they are all inefficient algorithms which have runtimes of O(n^2). One new perspective to evaluate the performance is to look at their average runtime, which we learnt this week. The average runtime is the average runtime of a function on random inputs. It turns out that insertion sort is the best algorithm among the three on average case.

    Nevertheless, these three algorithms are still considered bad sorting algorithms because of their inefficiency. Thus two new sorting algorithms are introduced in this week's lectures. They are quick sort and merge sort. With the concept of divide and conquer, these two algorithms achieve an impressive runtime of O(nlogn), which is much better than O(n^2) on large inputs. There's a very interesting visualization of the runtimes of all these sorting algorithms (Link: http://www.sorting-algorithms.com/). From this animation, you would have a good sense of how runtime varies in different sorting algorithms.

    There're also other sorting algorithms that could achieve the runtime of O(nlogn). However, most of them are hybrid algorithms from the basic algorithms I introduced above. For example, the built-in sorting algorithm of Python, which is Timsort, is a hybrid of merge and insertion sort algorithms.