gopythonrust

Quicksort is a sorting algorithm, same as bubblesort and mergesort. The algorithm for it employs a pivot with a divide-and-conquer approach.

Quicksort uses a pivot and partitions that are either smaller or larger than the pivot, followed by recursion on these partitions until all elements are sorted.

In clearer steps, here is what occurs during quicksort.

1. If the range of the partition is less than or equal to one, then there is nothing to sort, so return.
2. Choose a pivot. Assuming a randomized partition, choosing the first, middle, or last element are common selections.
3. Reorder elements such that those that are smaller than the pivot are positioned before it, and elements greater than it are positioned after it.
4. Recursively apply quicksort algorithm to the subrange before the pivot, as well as the subrange after it.

Here's what this might look like in code.

def quicksort(arr: list[int]) -> list[int]: # base case if len(arr) <= 1: return arr # choose last element in array pivot = arr[-1] # create sub array's based on comparison to pivot left = [ x for x in arr if x < pivot ] middle = [ x for x in arr if x == pivot ] right = [ x for x in arr if x > pivot ] # recursion return quicksort(left) + middle + quicksort(right) if __name__ == "__main__": arr = [1,3,2,8,5] print(quicksort(arr)) > [1,2,3,5,8]

Next, let us consider what the time and space complexities might be, starting with time first. We will consider the average case and the worst case.

On each call of quicksort, we iterate through the array three times. On the first iteration, this has complexity O(n). In the average case, an equal number of elements will be in left as well as right, giving size of each as n/2. There are two recursive calls, and so the recursive relation is:

From the master theorem for divide and conquer, we can simplify the right hand side to T(n) = O(n log n).

In the worst case, the array is already sorted, so one of left or right will have zero elements and the other will have n-1 elements. So we can see the time complexity will be:

This is the same as an algorithmic series, giving us a time complexity of O(n^2).

For space complexity, it's pretty much the same as time complexity. The average case is T(n) = O(n log n) and the worst case is O(n^2). However there exists more efficient quicksort algorithms that have an average space complexity of O(n) and some that operate in-place with space complexity O(1).