I fell ill this week, so unfortunately, I missed the Wednesday and Friday lecture. But the good news is, this week's suggested reading is incredible. (Thanks, Dan! Good choice!)
There are detailed diagrams with well elaborated explanations. There's code right under the diagram that lets you run it on the webpage itself. MC questions to make sure you understand the concept. What more to ask for?
As a minor detail, I noticed the selection sort in our course finds the minimum and insert it to the left instead of finding the largest and inserting it to the right.
When I saw O(n lg n) in the slides, I was confused as of where did lg n come from. So I started with the recommended reading. For merge sort, I found out that log n refers to the number of times you divide the list in half, where n is the length of the list. As an example, I found this from stack overflow:
"For example, starting from, say, 128 items, you divide into groups of 64, 32, 16, 8, 4, 2, 1 items -- 7 iterations (and log2(128) = 7)." (Source: http://stackoverflow.com/questions/10425506/intuitive-explanation-for-why-quicksort-is-n-log-n)
Also, n is related to the merge operation because you compare a leftlist[i] with a rightlist[j] at a time to get the smaller one, and the actual work is done where you append the smaller one in the list.
The mechanism of quick sort was harder to grasp than merge sort for me, so I'll let my mind process it a bit more before I read it again tomorrow.
No comments:
Post a Comment