Quick sort is considered as one of most efficient of all the sorting algorithms. The average case order of growth of quick sort is O (n log n). Though it has to be noted that the worst case order of growth of quick sort is O (n2).
The strategy behind quick sort is to consider one of the elements in the array as ‘pivot’ and then partition the remaining elements such that all the elements to the left of the ‘pivot’ element are less than or equal ‘pivot’ and all the elements to the right of the ‘pivot’ element are greater than ‘pivot’. This operation is performed recursively until all the elements in the input list are sorted.
// Input: An array of elements to be sorted denoted by ‘A’ and the size of the array denoted by ‘n’
// Output: In-place sorted array
// Requirement: The contents of the array to be sorted should be comparable with each other i.e. it is expected that relational operations can be applied on the contents of the array.
procedure sort (A, n)
quicksort (A, 0, n-1)
procedure quicksort(A, left, right)
if (left < right) then
pivotPos = partition (A, left, right)
quicksort (A, left, pivotPos-1)
quicksort (A, pivotPos+1, right)
// Input: An array and the low and high index within the array
// Output: The position of the pivot element. The contents of the array are arranged such that all the elements to the left of pivot are less than or equal to pivot and all the element to the right of the pivot are greater than pivot.
procedure partition (A, left, right)
// Consider the left most element as pivot
pivotPos = left
// Swap the pivot with the right most element
swap A[pivotPos] and A[right]
store = left
for i = left to right-1 do
if A[i] <= A[right] then
swap A[i] and A[store]
store = store + 1
swap A[store] and A[right]
Source Code snippet for the above Algorithm (in C++) is available at: Algorithms – Sorting – Quick Sort.
- Book: Introduction to the Design and Analysis of Algorithms by Anany Levitin. Copyright 2003, 0-201-74395-7.
- Book: Algorithms in a Nutshell by George T. Heineman, Gary Pollice, and Stanley Selkow. Copyright 2009 George Heineman, Gary Pollice, and Stanley Selkow, 978-0-596-51624-6.
- Wikipedia: http://en.wikipedia.org/wiki/Quicksort