The idea of Big O( ) is brand new to me. Big O( ) characterize a function's growth rate. For example, 2 n ** 2 and n ** 2 are both Big O(n**2) because when n doubles the running time will becomes 4 times longer for both cases. In other words, we don't need to care much about the constant, what we do need to care about is the main term.
When the size of length increases, the sorting time of Big O(1) will not increase because it is a constant time. From left to right, the increasing of sorting time will increase. When choosing the algorithm, we always want to consider the worst case instead of the best case. I think we should choose different algorithm depending on the input size. If the size is small, then the sorting time is basically the same and sometimes higher complexity algorithm can even be better. However, if the input size is really huge, we should probably give our priority to algorithms with lower complexity.
During lecture, Professor Danny introduced us some different sorting method. In order to make it easy to understand, he sorted the cards using different methods, which did help a lot. We compared four kinds of sorting algorithms in class and several other algorithms during lab. They are:
Selection Sort:
From Wikipedia: "The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right."
worse case: O(n**2)
average case: O(n**2)
best case: O(n**2)
n ** 2 comes because to find item for each position, we need to compare the others to find the smallest, i.e. total comparisons: n-1 + n-2 + ...... + 1
Insertion Sort:
From Wikipedia: "Sorting is typically done in-place, by iterating up the array, growing the sorted list behind it. At each array-position, it checks the value there against the largest value in the sorted list (which happens to be next to it, in the previous array-position checked). If larger, it leaves the element in place and moves to the next. If smaller, it finds the correct position within the sorted list, shifts all the larger values up to make a space, and inserts into that correct position."
worse case: O(n**2)
average case: O(n**2)
best case: O(n)
The best case is a nearly sorted list with only the last two positions in reverse order. We just need n-1 comparisons and 1 swap.
The worst case: each step we need n - 1 comparisons and 1 swap. Total steps: n + n-1 + .... => O(n**2)
Quick Sort:
form Wikipedia:
"The steps are:
- Pick an element, called a pivot, from the list.
- Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
- Recursively apply the above steps to the sub-list of elements with smaller values and separately to the sub-list of elements with greater values.
The base case of the recursion is lists of size zero or one, which never need to be sorted."
worse case: O(n**2)
average case: O(n lgn)
best case: O(n lgn)
Worse case comes from a sorted list, because the partition will not do anything for a sorted list.
Otherwise, petition will give us lgn, and in each partition, we need to compare n times, so it is (n lgn) times.
Merge Sort:
From Wikipedia:
"Conceptually, a merge sort works as follows:
- Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
- Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list."
worse case: O(n lgn)
average case: O(n lgn)
best case: O(n lgn)
The lgn comes from the partition step, and the n is because in each partition, all items need to be compared.
Count Sort:
def count_sort(L):
"""silly functional sort. See radix sort for something serious"""
count_list = [0, ] * len(L)
for i in L:
count_list[i] += 1
L1 = [] # blank slate!
for i in range(len(count_list)):
for j in range(count_list[i]):
L1.append(i)
return L1
For all cases, O(n), which means the running time is proportional to the length of the list.However, this function only works for lists that none of the numbers in the list is great than the length of the list.
I think a small change of the code will make it work for more cases. Here is my code:
def count_sort(L):
"""silly functional sort. See radix sort for something serious"""
count_list = [0, ] * (max(L)+1)
for i in L:
count_list[i] += 1
L1 = [] # blank slate!
for i in range(len(count_list)):
for j in range(count_list[i]):
L1.append(i)
return L1
Bubble Sort:
From Wikipedia:
"Starting from the beginning of the list, compare every adjacent pair, swap their position if they are not in the right order (the latter one is smaller than the former one). After each iteration, one less element (the last one) is needed to be compared until there are no more elements left to be compared."
best case: O(n**2)
worst case: O(n**2)
average case: O(n**2)
Actually, there is no difference between best case and worst case because before finishing the whole process, computer will never know whether this list is sorted. In each step, the computer needs to do comparisons and potential swaps. So, it is proportional to n**2 for all the cases.
The posted code for every algorithm is very helpful. Studying the code help me further understand how they worked. Also, some codes contains recursion which helped me reviewed recursion a little bit.
In real life, to choosing an algorithm, I think we also need to consider about memory space. I guess we will also study about this later.
