Quick Sort
Introduction
QuickSort is a divide and conquer algorithm. It picks an element as a pivot and partitions the given array around
the picked pivot. There are many different versions of quickSort that pick pivot in different ways.
1. Always pick the first element as a pivot
2. Always pick the last element as a pivot
3. Pick a random element as a pivot
4. Pick median as a pivot
Recursive QuickSort function
quickSort(arr[], low, high) {
if (low < high) {
pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
Example
def partition(l, r, nums):
# Last element will be the pivot and the first element the pointer
pivot, ptr = nums[r], l
for i in range(l, r):
if nums[i] <= pivot:
# Swapping values smaller than the pivot to the front
nums[i], nums[ptr] = nums[ptr], nums[i]
ptr += 1
# Finally swapping the last element with the pointer indexed number
nums[ptr], nums[r] = nums[r], nums[ptr]
return ptr
contd..
def quicksort(l, r, nums):
if len(nums) == 1: # Terminating Condition for recursion. VERY IMPORTANT!
return nums
if l < r:
pi = partition(l, r, nums)
quicksort(l, pi-1, nums) # Recursively sorting the left values
quicksort(pi+1, r, nums) # Recursively sorting the right values
return nums
example = [4, 5, 1, 2, 3]
result = [1, 2, 3, 4, 5]
print(quicksort(0, len(example)-1, example))
example = [2, 5, 6, 1, 4, 6, 2, 4, 7, 8]
result = [1, 2, 2, 4, 4, 5, 6, 6, 7, 8]
# As you can see, it works for duplicates too
print(quicksort(0, len(example)-1, example))
Output
[1, 2, 3, 4, 5]
[1, 2, 2, 4, 4, 5, 6, 6, 7, 8]
Time Complexity: Worst case time complexity is O(N2) and average case time complexity is O(N logN)
Auxiliary Space: O(1)