Sorting Algorithms
Sorting algorithms is an algorithm that puts the elements of a list in a certain order. It has two basic rules that the result must be in non-decreasing order and it is a reordering or permutation of the original input. There are many popular sorting algorithms and we can roughly make four categories for it, which are simple sort, efficient sort, bubble sort and distribution sort.
Selection Sort
Selection sort is simple but inefficient sorting algorithm. The algorithm make an addition empty list for the process. It looks for the largest or smallest item in the original list, then put it into the new empty list and find the next largest or smallest item in the remaining items in the original list. The new list is sorted, so when the algorithm is done, it returns the new list which has sorted data in it.
Efficiency: For selection sort it always performs О(n2).
Example code (from lecture notes):
def select(L):
"""Produce copy of L in sorted order
>>> select([3, 1, 2])
[1, 2, 3]
"""
L1 = L[:]
for i in range(len(L1)):
m = min(L1[i:])
j = L1.index(m,i)
L1[i], L1[j] = L1[j], L1[i]
return L1
Quick Sort
Quick sort use the divide-and-conquer strategy as well as the merge sort. Its advantage is it does not use additional storage but the disadvantage is it has bad performance against the list that can't be divided into halves. It chooses an element from the list which is called the pivot value. It compares the value next to the pivot value until the pivot value has been placed to the correct position. Then it becomes a split point, and split the list into two parts, which are the left half and the right half. All the values in the left half are smaller than the pivot value and all the values in the right half are larger than the pivot value. After that, it continues divide the two halves by the recursively algorithm until the final result comes out.
Efficiency: O(n log n) for the worst case and О(n2) for the best case.
Example code (from lecture notes)
def quick(L):
if len(L) > 1 :
return (quick([x for x in L[1:] if x < L[0]])
+ [L[0]] + quick([x for x in L[1:] if x >= L[0]]))
else :
return L
Merge Sort
Merge sort is an algorithm that improved by using divide-and-conquer strategy. It is a recursive algorithms and keep splitting the list into two halves. If the list is empty or has one item, it is sorted by the base case defined. If not, which the list has more than one item, it splits the list and recursively sort the both halves. In the end it combines the halves into a single and sorted list and that's why it is called the 'merge sort'. It is pretty efficient against very large lists.
Efficiency: O(n log n) in any case.
Example code (from lecture notes)
def merge(L1, L2):
"""return merge of L1 and L2
>>> merge([1, 3, 5], [2, 4, 6])
[1, 2, 3, 4, 5, 6]
>>> merge([1, 2, 3], [0, 4, 5])
[0, 1, 2, 3, 4, 5]
>>> merge([0], [1, 2, 3, 4])
[0, 1, 2, 3, 4]
"""
L = []
L1.reverse()
L2.reverse()
while L1 and L2:
if L1[-1] < L2[-1]:
L.append(L1.pop(-1))
else:
L.append(L2.pop(-1))
L1.reverse()
L2.reverse()
return L + L1 + L2
def merge_sort(L):
"""Produce copy of L in non-decreasing order
>>> merge_sort([1, 5, 3, 4, 2])
[1, 2, 3, 4, 5]
"""
if len(L) < 2 :
return L[:]
else :
return merge(merge_sort(L[:len(L)//2]), merge_sort(L[len(L)//2:]))
