Sorts and Efficiency (SLOG topic for Nov. 28th)

During the week of Nov.4^th, we had already come to the conclusion that the python built-in sort is the most efficient. Then it is quick sort and merge sort (with O(nlog n)), while selection sort being the least efficient (with O(n²)). Also during lab09, we were asked to run each different sort and record the time each sort took to sort a list with 1000, 2000, 3000, 4000, 5000, and 6000 items. We also repeated the same steps for sorted list as well as reverse sorted list. The results did match the race we did in class during the week of Nov. 4^th.

During the second half of the Wednesday class, we revisited the quick sort algorithm. Professor Heap pointed out that if we run quick sort on an already sorted list (reversed or not), it would take a longer time (the worst case scenario). In this case, instead of O(nlog n), quick sort would be O(n²). Normally, quick sort works by picking the first item as a pivot, arrange all the items with value lower than the pivot in one list, and all the value higher than the pivot in another list. Then it would call quick sort on the two separate lists. The main problem is that the algorithm always takes the first item as the pivot. If the list is already sorted, then one of the lists would be empty. Thus the divide-and-conquer method would not apply. In addition, python has a limit on the number of function calls. If the input is a sorted list with 10000 items, then quick sort would call upon itself 10000 times, which would probably exceed the call limit. In order to solve this problem, we modify the code such that it takes an arbitrary item as the pivot (by using the random module). When the size of the input is large, the probability of the pivot being the smallest or the largest is very small, thus it can solve the problem of sorting sorted list.