Quick sort discovered by C.A.R Hoare in 1962. It is a fast algorithm for internal or in-memory sorting except for sorting data in disk files.
Figure 1: Time and Space complexity of quick sort.
There are three basic steps:
- Partition the array or sub-array into left (smaller keys) and right (larger keys) groups.
- Call ourselves to sort the left group.
- Call ourselves again to sort the right group.
Choose a pivot value:
Ideally, the pivot should be the median of the item being sorted. We can pick up a element randomly from array. For simplicity, we usually pick the item on the right end or middle of the array.
Choosing the pivot is very important because it affects on performance. We expect that haft the items should be larger than the pivot, and half smaller. But, in worse cases, it has to sort one very large and one very small array. As a result, the large array takes more time to divide sub-arrays.
Quick implementation:
/**
* Implement quick sort algorithm refer to C++
* @param int a[] an array input unsorted.
* @param int left position of left side of the array.
* @param int right position of right side of the array.
*/
void QuickSort(int a[], int left, int right)
{
int i, j;
int x;
// Choose middle of array for pivot
x = a[(left+right)/2];
i = left;
j = right;
do{
while (a[i] < x) i++; // Loop until a[i] >= x
while (a[j] > x) j--; // Loop until a[i] <= x
if ( i <= j) // If found a[i] and a[j] unsorted
{
// Swap does not work in Java
// because of "Java is passed by value"
Swap(a[i], a[j]);
i++; // Move to next item
j--; // Move to preceding item
}
} while (i<j);
// Sort left side of array
if (left < j) QuickSort(a, left, j);
// Sort right side of array
if (right > i) QuickSort(a, i, right);
}
References:
- Robert Lafore, Advanced Sorting, in” Data Structures and Algorithms in Java “, Chapter 7. pp.333-356, Second Edition, Sams Publishing , 2003.
- Quicksort, Accessed at http://www.algolist.net/Algorithms/Sorting/Quicksort