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):
    # 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.

About the author

Arun Palaniappan