In addition to sorting algorithms we learned in CSC108, the prof talked about two new sorting methods in lecture: merge sort and quick sort. After reading through his slides a few times and sorting by hand a few short lists, I began to understand what the two sorts were. However, I didn't understand the run times that they had. Why were the run times for merge and quick sort both in O(n log n)? Are there n comparisons or log n comparisons? But apparently quick sort can have a quadratic run time if a bad pivot is chosen? I was extremely confused.
Thus, this post is not about detailing what bubble sort, insertion sort, selection sort, merge sort, quick sort, timsort and count sort do, but rather the tale of my self-learning.
When in trouble, always turn to Google.
At first, I read Wikipedia articles and other SLOG posts about sorting, but because I found the topic so dry I wasn't absorbing any of the information. Luckily however there are countless computer science videos on YouTube. I find myself someone that learns best when I someone is teaching me, so next to attending lecture videos were certainly the best option for me. With the help of some amazing YouTube channels, I was able to sort out my confusion. For merge sort and quick sort, there are log n splits of the list. However, with each sublist, each element in examined. Thus there are n examinations and log n splits, resulting in an O(n log n) run time. Pictures of merge sort were amazingly helpful also. Although I had worked out problems on paper, seeing very organized diagrams of the two sorts helped a great deal.
Image of how a list is split by merge sort.
Retrieved from http://www.codenlearn.com/
For anybody reading this SLOG post, I highly recommend the following videos! I found these to be the clearest and most helpful.
And, for some odd reason, this extremely entertaining Hungarian Dance of quick sort!
No comments:
Post a Comment