Just like Mergesort, Quicksort is another favorite sorting algorithm with best case O(n logn) but worst case O(n^2). However, compare to merge sort, this algorithm doesn’t use extra space at all. Find the article on wikipedia if you haven’t seen this algorithm yet: https://en.wikipedia.org/wiki/Quicksort
The idea is as below:
- Pick pivot number (any number, but someone said pick middle or random to minimize the worst case)
- Reorder the array so that elements less than pivot come before the pivot, and elements greater than pivot come after. After this, pivot is in its final position. This process is called partitioning.
- Recursively apply the above to sublists elements with smaller values and separately with greater values.
def quicksort(nums): sort(nums, 0, len(nums)-1) def sort(nums, first, last): if first < last: pivot = partition(nums, first, last) sort(nums, first, pivot-1) sort(nums, pivot+1, last) def partition(nums, first, last): pivot = first + (last - first + 1)/2 swap(nums, pivot, last) for i in range(first, last): if nums[i] <= nums[last]: swap(nums, i, first) first += 1 swap(nums, first, last) return first def swap(nums, left, right): nums[left], nums[right] = nums[right], nums[left]