Quicksort

Introduction

Invented in 1959/60 by the Turing award-winning British computer scientist, Sir Charles Antony Richard Hoare, Quicksort is one of the top 10 most influential algorithms of the 20th century. It is another recursive divide and conquer algorithm.

Quicksort is the fastest known comparison-based sorting algorithm for arrays in the average case.

Caveat: Merge sort works better on linked lists, and there are other non-comparison based algorithms that outperform Quicksort.

Pseudocode

1. Start with an array of n elements

2. Choose a pivot element from the array to be sorted

3. Partition the array into 2 unsorted subarrays, such that all elements in one subarray are less than the pivot and all the elements in the other subarray are greater than the pivot

4. Elements that are equal to the pivot can go in either subarray.

5. Sort each subarray recursively to yield two sorted subarrays

6. Concatenate the two sorted subarrays and the pivot to yield one sorted array.

Sir C.A.R Hoare in 2011

Quicksort taken from Wikipedia under CC-BY-SA 3.0