Home » Quick Sort

Quick Sort

Two partitions:

The Quick Sort uses a divide-and-conquer approach. It begins by breaking the original list into two partitions (sections) based on the value of some “pivot value”. One partition will eventually contain all the elements with values greater than the pivot value. The other will eventually contain all the elements with values less than or equal to the pivot value. (This description is not always completely true, but close.) Repeat this process on each partition.

Notice the word partition above. This is a salient feature of the Quick Sort. To identify this type of sort, look for the word “partition” (or equivalent term) in a rem or perhaps as a variable name.

Summary of how Quick Sort works:

A “pivot value” is selected. Usually this is the element at the center position of the array. Elements in the array are moved such that all elements less than the pivot value are in one half (partition) and all elements larger than or equal to the pivot value are in the other half (partition). This process is continually repeated on each partition. The partitions become smaller until they each consist of just a single element. At that point the array is ordered.

Used in Array.sort( ):
The Quick Sort is used on primitive arrays passed to Arrays.sort( ); however, the Merge Sort is used on object arrays.