Quicksort, when properly implemented is on average the fastest known general-purpose sorting algorithm. Although it is extremely fast, it is also very complex. This recursive sort first selects a value called the pivot. If we assume that there are k values within the array to be sorted, which are less than the pivot, these keys must be arranged so that they are placed in the first k positions in the array. Likewise all the keys greater than the pivot are grouped to the last array_size - k positions in the array. The pivot itself is placed in the k position of the array. These partitions to the left and right of the pivot, need not be sorted in any particular order.
public class QuickSort {
int pivot, left1, right1;
public void qSort (int array[], int left, int right) {
left1 = left;
right1 = right;
pivot = array[left];
while (left < right)
{
while ((array[right] >= pivot) && (left < right))
right--;
if (left != right)
{
array[left] = array[right];
left++;
}
while ((array[left] <= pivot) && (left < right))
left++;
if (left != right)
{
array[right] = array[left];
right--;
}
}
array[left] = pivot;
pivot = left;
left = left1;
right = right1;
if (left < pivot)
qSort(array, left, pivot-1);
if (right > pivot)
qSort(array, pivot+1, right);
}
public static void main(String[] args) {
int array[] = {6, 3, 5, 4, 9, 2, 7};
int left = 0;
int arraySize = 7;
int right = arraySize -1;
String output;
QuickSort qsort = new QuickSort();
qsort.qSort(array, left, right);
for(int i=0; i < arraySize; i++) {
System.out.print(array[i] + " ");
}
}
}
The Quicksort function will first swap the pivot to the end of the array, then parition the array. The partition function uses a left and right index to moves forward and backward, respectively, through the array. The first while loop (left index) ends whenever a key larger than the pivot is encountered. The position of the key is stored in left. The second while loop (right index) ends whenever a key less than the pivot is encountered. The position of the key is stored in right. Then these two keys are swapped. This keeps all the keys less than the pivot on the "left side" of the array and all the keys greater than the pivot on the "right side" of the array. The process continues until the do-while loop ends -when the two indices cross. However before the do-while loop is exited a swap is performed. This swap (which does not need to be performed) is undone immideately afterwards. The position of the first key in the right partition is returned to Quicksort and then the pivot is swapped to the correct (middle) position in the now completely partitioned array.
Now, Quicksort is called recursively once for each partition. Within these new calls, a pivot for each partition is chosen and the partitions themselves are partitioned! This process continues until the new partitions only have 0 or 1 element within them. Here is an example:
6 3 5 4 9 2 7
Pivot - 5, First Partition:
6 3 7 4 9 2 5
6 3 7 4 9 2 5
2 3 7 4 9 6 5
2 3 4 7 9 6 5
2 3 7 7 9 6 5
2 3 4 7 9 6 5
2 3 4 5 9 6 7
Quicksort, now continued by analyzing analyzing partitioning the partitions (2, 3, 4) and (9, 6, 7). This process is continued until the new partitions have 0 or 1 key within them.
|
