Quicksort is a popular sorting algorithm for sorting arrays and lists. It is a comparison sort, meaning it sorts by comparing two elements at a time. It has a O(n log n) running time on average, but may have a quadratic running time for some inputs.
Algorithm[]
Quicksort works by recursively partitioning the array into ordered partitions.
- Given a list of values arr, pick an element i out of the list, order all the elements smaller than of equal to i before it, and all the elements larger that i after it.
- Apply (1) to all elements before i and all elements after i.
- Finish when all lists are one or zero elements in size.
The element i is called the pivot, and it's selection is important for the performance of the algorithm.
Pivot Selection[]
One way to select the pivot is to get the middle value. There techniques however will cause the sorting to have a quadratic running time for some inputs. To avoid these situations some implementations randomize the pivot selection, making the quadratic running time improbable.
Pseudocode[]
Input: a list of values, arr.
quicksort(arr):
if arr is empty:
return arr
p = pickPivotFrom(arr)
lesser = arr.elementsSmallerOrEqual(p)
greater = arr.elemetsGreater(p)
return concatenate(quicksort(lesser), pivot, quicksort(greater))
Criticism[]
Quicksort is not a stable sort. Which means that equal objects can have their order changed within the sorted list. It's complexity can sometimes be quadratic due to bad pivot selection, but despite these problems,it often outperforms it's main competitors - mergesort and heapsort.
See Also[]
| Sorting algorithms |
|---|
| Bubble sort - Insertion sort - Merge sort - Quicksort - Selection sort - Heap sort |