Week 11 - Sorting and Efficiency

Actually, the topic about several ways to sort a list and their efficiency was discussed when i was learning CSC108. These weeks' lectures and labs let me get familiar with some more advanced sorting codes. The select sort is just like the one i learnt in 108 lecture and the efficiency was quite low. The quick sort and the merge sort can work much more efficiently; for example, in a case of sorting 1000-length list, these two are 10 times faster than select sort. One thing which is a little interesting is that if you want to sort a sorted list with quick sort, you will spend long time on it. It looks weird, but after analyzing the codes, i understand that the time spend on sorting is depend on the choice of pivot; so, if you choose the first item as pivot, the program will go through the list one by one which make that weird thing happen. I feel very excited about built-in sort, because it works so fast even if the length of random list is over 1000000. However, the count sort introduced by professor can defeat built-in way, if the length keeping growing, but it is a kind of trick which can not be used in general case. I do not know how built-in sort works, but Well, that is why built-in sort is built in.

Week 10

Week 9

Week 8

In lecture, we have talked about linked list and tree for several weeks. Generally, i think they have some similar parts; for example, the first parameter after self are all the value of that linked list or tree, and the following parameter is another linked list or tree. These two are quite organized ways to store data. Especially for linked list, it so convenient to mutate single linked list whatever it is hear, tail or in middle. Not like a regular list which is almost impossible to prepend some value without spending plenty of time. Because in linked list, prepend and pend are the same thing, they just take one step, not one step + shifting every original term in regular list.