QuickSort
Description
Choose any element to act as a pivot and place it in the correct location with all numbers less than it on the left and numbers greater on the right. Recursively repeat this process on the left and right subarrays created by the pivot.
Complexity Analysis
Average case | \( O(nlogn) \) |
|---|---|
Best case | \( O(nlogn) \) |
Worst case | \( O(n) \) |
Space Complexity | \( O(n) \) |
def partition(arr, low, high):
# Default pick last element to be pivot
pivot = arr[high]
i = low - 1
# Partition all elements less than pivot to be on the left side
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[j], arr[i] = arr[i], arr[j]
# Place the pivot in correct location
arr[i+1], arr[high] = arr[high], arr[i+1]
return i+1
def quickSort(arr, low, high):
if low < high:
idx = partition(arr, low, high)
quickSort(arr, low, idx - 1)
quickSort(arr, idx+1, high)
return arrGeoffrey Lee