Algorithms – Sorting – Quick Sort

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.

Algorithm:

// 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)
end

procedure quicksort(A, left, right)
    if (left < right) then
        pivotPos = partition (A, left, right)
        quicksort (A, left, pivotPos-1)
        quicksort (A, pivotPos+1, right)
    endif
end

// 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
        endif
    done
    swap A[store] and A[right]
    return store
end


Source Code snippet for the above Algorithm (in C++) is available at: Algorithms – Sorting – Quick Sort.


Reference:

  • 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
Advertisements

One thought on “Algorithms – Sorting – Quick Sort

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s