Week 11: Sorting and Efficiency

Sorting and efficiency is the last topic that is covered in CSC148, we were able to touch on this a little bit in CSC108. However, with the introduction to recursion, we were taught two more sorts that take advantage of this for a faster run time.

The run time of O(n) is the best for most sorting algorithms in existence, although the best ones have O(nlogn) as the worst case. One important take away from the analysis of various sorts is the efficiency, or the complexity of an algorithm, specifically iterative (insertion, selection, and bubble) and recursive (quick and merge) algorithms. This shed a light in the implementation of functional software, as I saw in the lab, although the change of one iterative or recursive step has barely any impact in the running time of an algorithm, it could play a significant part in a larger-scaled project. For instance, as we see in the first three sorts we learned, they were all running at O(n²) as their average and worst case, which is really bad because as the size of the list increase, the algorithms will run quadratic times the amount of increase. Quick and merge sort are much faster in the sense that their average run time is O(nlogn), however, as we see in the class, quick sort is not exactly stable as a terribly organized list could cause it to exceed max recursion depth.

What was interesting to me and my friends are the custom sorting algorithms we were playing around with in the lab, including comb sort and cocktail sort. Their animation was really intriguing, some sorts from the left, others from the right, there are even those that sort from the sides or start at the middle.

Out of the three major sub-topics we discussed this term, big-oh was actually the topic I paid the least attention to in high school, mainly because it was at the end of the term and we did not really get in depth into it. Although we were taught shell sort, heap sort as well as quick3 sort in addition to the basic five, we were never tested or worked on them. I was not very clear why at the time but now that we learn the exact same five sorts in the first year of CS, it seems like the other three common sorts are a little more complex and I hope to learn about them more in future years.

What we did was to implement a user interface in which one could select a sorting algorithm: bubble sort, insertion sort, selection sort, merge sort and quick sort. It was a big give away at the time since the codes for these common types of sorts are all over the internet, and obviously I did not pay much attention to the code itself. But we were instructed to show display for sorting on 10 integers as well as time the sorting process for 10000 randomly generated integers. Even though I did not take away much from this particular project back then, it definitely established a base for me in the field of sorting and efficiency.