Sorting is a method that change the sequence of a list in the order that we want to. For example, we can sort a list of numbers: [5,2,7,8,4,9,6,3,1] by calling the python build-in method '.sort()' to arrange it in to [1,2,3,4,5,6,7,8,9]. This method also can be applied in a list of letters. However, python build-in methods have some limits. It can only sort particular things that has a certain order. Therefore, we must other methods to finish that. It remains that in CSC108 we have already experienced some methods of sorts such as selection sort, bubble sort and insertion sort. Those sorts have their own way. The way the compare items is different with each other. So there's another problem emerged-- Efficiency. The step of those sort method is different. For example, in merge sort, the idea is to divide the list in half and then merge sort the halves then merge the sorted results. There is two variables, times of splitting the list and the steps that each time we split. Less steps means less time to run it then it is more efficient. To be accurate, let's take look on some data.
This is what we did in this week's lab. It is obvious to see that the different method has different runtime when they have a some list. Form this table, we can tell that the python build-in method sort() is the most efficient method.
Meanwhile, we just compare this table vertically. We also can compare it horizontally. With the increasing of length, the time of all of methods increased. But they increased at different rate.
Some are increasing exponentially. Some are increasing linearly. This is what we learnt the Big O.
It is like the Big O in CSC165. It talks about the runtime at worstcase. g
∈O(f) means “g grows no faster than f” (or equivalently, “f is an upper bound for g”).
