The Quick Sort

The Quick Sort is, on average, the fastest known sorting algorithm.
Choose an element of the list to be the pivot element.
- Choose the first element, or
- Choose the last element, or
- Choose the middle element, or
- Choose a random element, or
- Choose the median of a small number of random elements.
The Quick Sort is at its fastest when the pivot is the element that belongs in the middle of the list.
The Quick Sort is at its slowest when the pivot is the element that belongs at one end of the list.
The list is divided into four regions.
- Smaller region: The elements determined to be less than the pivot.
- Equal region: The elements determined to be equal to the pivot.
- Larger region: The elements determined to be greater than the pivot.
- NotDone region: The elements that have not yet been compared to the pivot.
The regions are arranged in the order Smaller region, Equal region, NotDone region, Larger region, from left to right.
Initially, all elements are in the NotDone region.
Eventually, all elements will be in the other three regions.
Establish three indexes.
- smallerR - Index of rightmost member of Smaller region.
- notDoneL - Index of leftmost member of NotDone region.
- largerL - Index of leftmost member of Larger region.
Initial Values
- smallerR is one less than the lowest subscript in the array.
- notDoneL equals the lowest subscript in the array.
- largerL is one greater than the highest subscript in the array.
Compare the element in position notDoneL to the pivot element.
- If it is less than the pivot,
  - Increment smallerR,
  - Swap the elements in the notDoneL and smallerR positions.
  - Increment notDoneL.
- If it is equal to the pivot,
  - increment notDoneL.
- If it is greater than the pivot,
  - Decrement largerL.
  - Swap the elements in the notDoneL and largerL positions.
Continue until the NotDone region is empty.
Then apply the process recursively to the regions Smaller and Larger.
The run time is of order n log n (with probability near 100%).
Example - QuickSort.cpp.

Return to Lectures page

This page was last modified on Apr 23, 2001

URL: http://people.hsc.edu/faculty-staff/robbk/Coms262/Lectures/QuickSort.html