During week 10 and week 11, we analyzed some sorting method and their efficiency combined with the knowledge that is learned in CSC165 course, which is the big-oh notation.
The sorting methods include tim sort, which is the python build-in sorting method, insertion sort, selection sort, merge sort, bubble sort and quick sort as well.
In csc108, we focus on bubble sort, insertion sort and selection sort. Bubble sort, as the name shows, simply compare each adjacent pair in the list that is wait to be sorted and shift the largest item so far to the position with index -1. Its runtime belongs to O(N^2), which shows that its run time grows quadratically when the input size doubles. As for insertion sort, we choose each of the item in the list that is wait to be sorted and insert the item to the correct position in the sorted part. The difference between insertion sort and bubble sort is that the sorted part of the bubble sort appears at the end of the list but the sorted part of insertion sorted is located at the front of the list. The same as the bubble sort, the runtime of insertion sort also grows quadratically but it's more efficient compared with the bubble sort when the length of the list that is wait to be sorted are very large. The last sorting method that is discussed in the csc108 course and it’s also mentioned in the csc148 course is selection sort. Selection sort focus on each of the item in the list and exchange the item and the smallest item in the remaining part that has not been sorted yet. The runtime of selection sort also grows quadratically with runtime n belongs to O(n^2).
Now move on to the new knowledge that is learned in the csc148 course. Quick sort, which is a new sorting method to me, chooses the pivot item and find the items in the list that are smaller than the pivot item and the items that are less than the pivot item, and the rearrange the order of the items in the list. Finally, apply the same sorting method recursively. Here is some code for this recursive idea:
quick([x for x in L if x < L[i]]) + [L[i]] + quick([x for x in (L[0:i] + L[i+1:]) if x >= L[i]])
Where L[i] is at its final position of the list and the former part and the later part are waited to be sorted. The base case for this sorting method is that when the length of the list is smaller than 2, there is no need to sort the list and therefore we can just return the list when this condition satisfies. And here is the example:
if len(L) < 2:
return L[:]
Even though I understand how quick sort runs, I do not understand why the runtime for quick sort can belong to O(n log n), is that simply because the use of recursion?
To find the reason for it, I did some research on the internet and it shows that for each of the partitioning operation of the sorting method, it will take O(n) iterations and the number of the partition is logn, so after combining them together, the final result becomes O(n logn). Unfortunately, I was not fully understand this idea when doing the test, and failed to answer the question.
As for the merge sort, it consists two part, one of them can be treated as a helper function and It is named merge(), which takes two parameter and each of them is a list. For this helper function, a new empty list is created and them compare the first items in the two given list and append the smaller one to the new empty list. And this step continues until one of the list becomes empty, then combine the list together as the following shows:
return L + L1[i1:] + L2[i2:]
Since one of L1[i1:] and L2[i2:] is already empty, we do not need to worry too much and L is the already sorted part.
The idea of the main function of the merge sort is that we split the given list to two equal pieces and apply the helper function to them:
merge(merge_sort(L[:len(L)//2]), merge_sort(L[len(L)//2:]))
Where the base case is the same as the base case in the quick sort since when the length of the given list is less that 2, there is no need for us to sort the list again. And the worst case performance is O(n log n) since it also involves dividing the list to two pieces and the number of iterations of the helper function grows linearly.
To talk about the test this week, I did not do quite well during the test since I do not understand the sorting methods at that moment and therefore fail to explain the reason why it is O(n log n) and I soon understand the concept after the test:(.
Good luck for the final exam :)
No comments:
Post a Comment