Truly Understanding Quicksort

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.

Leave a comment

Your email address will not be published. Required fields are marked *