Quicksort is a [[divide-and-conquer]] [[algorithm]] to [[sort]] an array in place. Quicksort divides an array in two sides around a **pivot** element. Everything less than the pivot is placed in the low side of the array, and everything greater than the pivot is placed in the high side. Thus the pivot ends up in the correct location. Quicksort is called [[base/Algorithms/recursion|recursively]] until the array is sorted. The pseudocode for quicksort might be ```python quicksort(A, left, right): # specify basecase if right - left < 2: if right < left: swap(right, left) # choose a pivot x = A[right] # partition array A on pivot, return position p = partition(A, right) # quicksort again quicksort(A, left, p-1) quicksort(A, p+1, right) ``` The magic of quicksort is the `partition` algorithm. There are multiple implementations of `partition`, a common one is the Lomuto partition scheme, named after the Italian computer scientists who invented it. In the Lomuto scheme, the pivot is the last element in the array. Two regions are maintained: the region `A[1:i]` is the lower side, the region `A[i+1:j-1]` is the higher side, and `A[j:n-1]` is the unsorted region (the final element `A[n]` is the partition element). Compare each element `A[j]` in the unsorted region with the pivot `A[n]` and place it into the lower or upper side according to its value until the array is fully partitioned. To add to the upper side, simply increment the pointer to the end of the upper side. To add to the lower side, swap the element with the first element in the upper side `A[i+1]` and increment both pointers. Finally, swap the pivot element with the first element in the upper half and return the index of the pivot element. ```python partition(A, n): i=0 for j=1 to n-1: if A[j] < A[n]: # place element in lower side swap(A, i+1, j) i += 1 j += 1 else j += 1 swap(A, i+1, A[n]) return i+1 ``` The running time of the Lumoto partition is $O(n)$ as it simply traverses the array once for each partition. ## complexity of quicksort The **ideal goal** of quicksort is to create a balanced partition on each recursion. With perfectly balanced partitions, the running time is as low as $\Theta(n \log_2 n)$. With an array that is already sorted in reverse, running time will be $\Theta(n^2)$. By using [[randomness]] when selecting a pivot, the average running time can be shown to be $\Theta (n \log_2 n)$ so long as the split has constant proportionality (even if the proportionality is not balanced). Quicksort was invented by Sir Tony Hoare.