Sorting and Efficiency

In the past few weeks we have revisited some previously learned sorting algorithms: Selection, Insertion and Bubble sorts and also learned some new sorts like Quick, Merge and Python's built in Timsort.

Rather than just learning the concept and implementations of these algorithms, we looked instead at the 'efficiency' of these algorithms. Efficiency is, in essence, measured in the time and space complexity of the algorithms. We focused on time complexity - the typical run-time of the algorithm and specifically, the upper bound on this run-time (the worst case, denoted using Big-Oh).

We saw that bubble and insert have the smallest time complexity in the best case (the case of an already, or nearly, sorted list) of big O of n, or O(n). But, in the worst case (a reverse sorted list) they fare worst with a time complexity of O(n^2)

Selection sort, as expected, came out at bottom with best and worst case time efficiencies of O(n^2).

Having worked with these algorithms before, the results weren't all too surprising. What was interesting though was seeing how small changes in their Python implementations could speed up their runtimes (though time complexity remains the same). For instance, calls to repeated calls to len (in loops) would slow down the runtime but this could be remedied by introducing a temporary variable to only have to call len once.

Other tweaks to improve runtime were less useful: Trying to end bubble sort early by seeing if the last scan of the list had any swaps didn't cause a significant boost to runetime.

Ofcourse, the most interesting part of the last few weeks has been working with mergesort and quicksort. I will breifly re-iterate their algorithms in my own words and the comment on any interesting aspects of them.

Both of these new algorithms are recursive. Mergesort cuts the list to be sorted into two halves, then recursively calls mergesort on the halves and finally, 'merges' the two halves back into a single list. The splitting into two halves has a time complexity of log(n) and the merge operation runs in time complexity of n. So altogether mergesort runs in best and worst case of O(nlog(n)). Like the previous algorithms, we also explored ways to speed up mergesorts runtime: By continually updating the original list and not replacing it, we were able to significantly cut down average runtime (though still O(nlog(n) ofcourse).

Quicksort first chooses a 'pivot' (any item in the list) and then splits the list into two galves: items bigger than pivot and smaller than pivot. It then (recursively) calls quicksort on the two sub lists. Quicksort is nearly identical in time complexity to mergesort except in the worst case it has a time complexity in O(n^2). We explored a similar improvement technique as the one to mergesort but it yeilded no benefits for quicksort.

All in all, this part of the course really helped solifidy my understanding of these sorting algorithms - we really got into the fundamental workings of them, took them apart, analysed them, compared them to others and explored techniques of improving them.