Data Structures & Algorithms

What is Quicksort?

Quicksort is one of the efficient sorting algorithms. The algorithm performs sorting by applying the divide and conquer paradigm. Consider an array A[1…n] of n elements. The algorithm divides the array A on an index q such that all elements in the sub-array left of the index are lesser than the element in the index q (A[q]), and all elements in the right subarray are greater than A[q]. Now, the algorithm recursively sorts the two subarrays A[1..q-1] and A[q+1..n] inplace by calling the quicksort function. To obtain the index q, the algorithm uses a partition function.

The partition function is a function that takes in an array A[l..u] as input. Here, l is the lower bound, and u is the upper bound of the array. The algorithm finds an index q such that all elements less than A[q] fall in the subarray A[l..q-1], and all elements greater than A[q] fall in the subarray A[q+1..u]. The partition function achieves this by using a pivot element and two pointers – pointer i and pointer j to the array.

Pointer j points to the first element in the array, and the pointer i is initialized as j-1. The function iterates through the array using pointer j. For element A[j], the element can be greater than the pivot element or less than the pivot element. If the element is greater than the pivot element, pointer j gets incremented, pointing to the next element. If the element A[j] is less than the pivot element, we increment pointer i, swap A[i] and A[j]. The swapping of the elements helps maintain the pointer i such that the elements up to the element pointed by pointer i are less than the pivot element. As a final step, the partition function swaps the pivot element with the element at index i+1, thereby moving the pivot element in the correct position in the partitioned array.

Source Code

def partition(arr, lb, ub):
# The last element of the array is taken
# to be pivot element
pivot_elt = arr[ub-1]
i = lb - 1
for j in range(lb, ub):
# If the element is less than pivot element
if arr[j] <pivot_elt:
# Swap the elements so that the elements
# arr[lb..i] is always less than pivot element
i = i + 1
arr[i], arr[j] = arr[j], arr[i]
# Final swap of the pivot element and arr[i+1]
# to put the pivot element in place
arr[i+1], arr[ub-1] = arr[ub-1], arr[i+1]
return i+1

def quick_sort(arr, lb, ub):
if(lb<ub):
# Recursively sorting the array
q = partition(arr, lb, ub)
arr = quick_sort(arr, lb, q)
arr = quick_sort(arr, q+1, ub)
return arr

if __name__ == "__main__":
arr = [3, 7, 9, 2, 5, 0]
n = len(arr)
arr = quick_sort(arr, 0, n)
print (arr)

The best-case time complexity of quicksort is O(n log n). In the best-case scenario, in each call to the algorithm, the algorithm divides the problem into two subproblems of equal size. The worst time complexity of the quicksort algorithm is O(n^2). This occurs when the partition element is always chosen as the last element, and the array is already sorted.