Read this in other languages: English, Português
Quicksort is an efficient comparison sort algorithm devised by Tony Hoare in 1959. It features a Divide and Conquer design, and works by recursively partitioning and reordering the input array according to a pivot element.
Quicksort presents a slightly better performance than other comparison sort algorithms such as Merge Sort and Heapsort.
Quicksort presents quadratic complexity when dealing with an array filled with duplicate keys. It can be modified by using a 3 way partitioning algorithm, making this case linear instead.
- If the array is shorter than two elements, stop recursing.
- Select an element in the array and call it the pivot element.
- Partition and reorder the array into two sub-arrays, such that the elements that are less than the pivot come before the division point and elements greater than the pivot come after it. Elements that equal the pivot can be placed on either of the partitions.
- Recursively apply Steps 1 -- 3 in the the left and right sub-arrays.
- When the recursion ends, the array is sorted.
For dealing with duplicate keys, step 3 uses 3 sub-arrays instead, such that the elements that are less than the pivot are placed in the first sub-array, the duplicate keys are palced in the second sub-array, and the elements greater than the pivot are placed in the third sub-array.
- Best-Case:
$O(n \log_2 n)$ comparisons - Worst-Case:
$O(n^2)$ comparisons
- Desenvolvendo Software (Portuguese)
- Wikipedia