Learn about merge-sort, quick-sort, other sorting algorithms and their running time.
- Merge-Sort uses divide-and-conquer algorithmic design pattern to sort a sequence S with n elements.
- Divide: If the input size is smaller than a certain threshold, solve the problem directly using a straightforward method and return the solution. Otherwise, divide the input data into two or more disjoint subset.
- Conquer: Recursively solve the subproblems associated with the subsets.
- Combine: Take the solutions to the subproblems and merge them into a solution to the original problem.
# In Python # Merge two sorted Python lists S1 and S2 into properly sized list S def merge(S1, S2, S): i = j = 0 while i + j < len(S): if j == len(S2) or (i<len(S1) and S1[i] < S2[j]): S[i+j] = S[i] # copy ith element of S1 as next item of S i += 1 else: S[i+j] = S2[j] # copy jth element of S2 as next item of S j += 1 # Sort the elements of Python list S using the merge-sort algorithm def merge_sort(S): n = len(S) if n<2: return # list is already sorted # Divide mid = n // 2 S1 = S[0:mid] # copy of first half S2 = S[mid:n] # copy of second half # Conquer (with recursion) merge_sort(S1) # sort copy of first half merge_sort(S2) # sort copy of second half # Merge results merge(S1, S2, S) # merge sorted halves back into S
- Algorithm merge-sort sorts a sequence S if size n in \(O(n\log n)\) time, assuming two elements of S can be compared in \(O(1)\) time.
Description of Quick-sort
- Quick-Sort algorithm uses divide-and-conquer technique to sort a sequence S using a simple recursive approach.
- Divide: If \(S\) has at least two elements, select a specific element \(x\) from S, which is called the pivot.
Remove all the elements from \(S\) and put them into three sequences:
- \(L\), storing the elements in \(S\) less than \(x\)
- \(E\), storing the elements in \(S\) equal to \(x\)
- \(G\), storing the elements in \(S\) greater than \(x\)
- Conquer: Recursively sort sequences \(L\) and \(G\).
- Combine: put back the elements into \(S\) in order by first inserting the elements of \(L\), then those of \(E\), and finally those of \(G\).
# In Python # Sort the elements of queue S using the quick-sort algorithm def quick_sort(S): n = len(S) if n<2: return # list is already sorted # Divide p = S.first() # using first as arbitrary pivot L = LinkedQueue() E = LinkedQueue() G = LinkedQueue() while not S.is_empty(): # divide S into L, E, and G if S.first() < p L.enqueue(S.dequeue()) elif p < S.first(): G.enqueue(S.dequeue()) else: E.enqueue(S.dequeue()) # Conquere (with recursion) quick_sort(L) # sort elements less than p quick_sort(G) # sort elements greater than p # Concatenate results while not L.is_empty(): S.enqueue(L,dequeue()) while not E.is_empty(): S.enqueue(E.dequeue()) while not G.is_empty(): S.enqueue(G.dequeue())
- Quick-Sort runs in \(O(n\log n)\) time, and \(O(n^2)\) in the worst-case.
- Randomized Quick-Sort gives \(O(n\log n)\) expected running time.
- Memory: \(O(\log n)\)
- In bubble sort, we start at the beginning of the array and swap the first two elements if the first is greater than the second
- Then, we go to the next pair, and so on, continuously making sweeps of the array until it is sorted.
- Runtime: \(O(n^2)\) average and worst case, Memory: \(O(1)\).
- Selection sort is simple but inefficient.
- Find the smallest element using a linear scan and move it to the front (swapping it with the front element).
- Continue doing this until all the elements are in place
- Insertion sort is relatively efficient for small lists and mostly sorted list.
- It works by taking elements from the list one by one and inserting them in their correct position into a new sorted list.
- Runtime: \(O(n^2)\), Memory: \(O(1)\)
- Heap sort works by determining the largest (or smallest) element of the list, placing that at the end (or beginning) of the list.
- Then, continuing with the rest of the list by using a data structure heap (a special type of binary tree).
- Runtime: \(O(n\log(n))\), Memory: \(O(1)\)
- Radix sort is a sorting algorithm for integers that takes advantage of the fact that integers have a finite number of bits.
- We iterate through each digit of the number, grouping numbers by each digit.
- Then, we sort each of these groupings by the next digit.
- Runtime: \(O(kn)\) (\(n\) is the number of elements and \(k\) is the number of passes of the sorting algorithm)
Comparison and Non-comparison Sort
- Comparison sort is a type of sorting algorithm that only reads the list elements through a single comparison operation and
determines which of two elements should occur first in the final sorted list.
- Comparison: \(a_i < a_j, a_i \leq a_j, ...\)
- Examples : Bubble sort, Insertion sort, Selection sort, Quick sort, Heap sort, Merge sort, Odd-even sort, Cocktail sort, Cycle sort, Merge insertion sort, Smoothsort, Timsort
- Limitations of Comparison Sorting
- To sort \(n\) elements, comparison sorts must make \(\Omega(n\log n)\) comparisons in the worst case.
- That is a comparison sort must have lower bound of \(\Omega(n\log n)\) comparison operations, which is known as linear or linearithmic time.
- Non-comparison sort perform sorting without comparing the elements rather by making certain assumptions about the data.
- Counting sort (indexes using key values)
- Radix sort( examines individual bits of keys)
- Bucket sort( examines bits of keys)
- These are linear sorting algorithms.
- They make certain assumptions about the data.
Sorting Algorithm Comparison