Introduction
Quicksort is a sorting algorithm, that is, it takes an array of values as input and it permutes them such that they are in increasing order.
Example
Input:
7 2 8 4 3 6 9
Output:
2 3 4 6 7 8 9
Why study Quicksort?
Quicksort is very interesting to study and truly understand because of several features:
- It is very fast, both in practice and in theory. It can achieve a time complexity of O(n log n) on average, which is known to be the best possible complexity for comparison-based sorting algorithms.
- It is an example of an in-place sorting algorithm. This means it does not use additional memory for the output or for processing, making it ideal in situations where memory is limited.
- It is cache-friendly, making it very fast to execute on modern computers.
- It is an example of a recursive algorithm, making it pedagogically important.
- The algorithm is challenging to truly understand. When you finally get it, you will have an “Eureka” moment.
- It is historically important, as it was one of the first O(n log n) algorithms for sorting.
Go to the next page for an overview of how quicksort works.