In this post, we will look in to the Quicksort in Java and its different implementations. Like Mergesort, Quicksort is a Divide and Conquer algorithm.
Quicksort algorithm is one of the most used sorting algorithm based on the Divide-and-Conquer algorithm. It work by dividing the input in the 2 sub problems and sorting the both side recursively. This algorithm picks one of the element as Pivot and partition the input around the Pivot. There are different variations of choosing the Pivot element:
The core concept of Quicksort algorithm is the partition logic. Once we pick the Pivot element, we group the input into 2 parts and place the Pivot on the correct position so that
We sort the both side recursively by repeating the above step (Choose Pivot and put Pivot in the correct position). Before we get in to the Quicksort implementation, let’s see how this work using one example. Let’s take this array as an input:
Let’s choose the Pivot element, in this example, we will choose last element as a pivot. Once we choose the pivot, we will position the pivot element to its correct position so as all element less than pivot are on the left-hand side while element greater than the pivot element are on the right-hand side. On the first iteration, this is how our array look like:
We know this process as Partitioning and it’s the core concept of the Quicksort algorithm. There are multiple ways to partition the input. In our example, we will start with the following steps
Let’s see this in action:
Pay close attention to the pIndex position. Once we swapped the elements, we incremented the pIndex so trek the next element which should be moved to the right of pivot.
We repeat this process we reach at the end. Once we reach at the end, we swap the pivot element with the pIndex to move the pivot to its sorted position (Pivot is at the sorted element and we left with sorting the right and left side of the pivot)
With Quicksort, we recursively sort the left and right side of the input by selecting the new pivot element and sorting this pivot to its correct position. At the end of each iteration, we recursively sorting the left and right side of the input.
Let’s look in to the pseudo-code if you want to implement the Quicksort in Java:
quickSort(array[] input, start, end){
if(start < end){ // we only want to run it till we are not at the end of the input
position = partition(input, start, end); // position show the correct place for the pivot element
quickSort(input, start, position-1); // we will recursively sort the left side of the pivot
quickSort(input, position+1, end) // sort the right side of pivot
}
}
/**
* partition is the core of the quick sort algorithm
*/
partition(array[] a, start, end){
pivot = a[end]; // we picked the last element as pivot
pIndex = low;
for(i = start; i<=end-1; i++){
if(a[i] <pivot){
swap(a[pIndex], a[i]);
pIndex++; // we moved the position to next element
}
}
// when reached at the end, let's swap the pivot and pInex
swap(pivot,pindex);
return pIndex;
}
Let’s see Quicksort in Java by choosing the last element as the pivot element.
public class QucikSortAlgo {
public static void main(String[] args) {
int[] array = {17,41,5,22,54,6,29,3,13}; // initial input
array = quickSort(0, array.length-1,array);
for (int i =0; i< array.length; i++){
System.out.println(array[i]); // print the response
}
}
/**
* The main quickSort method
* */
public static int[] quickSort(int start, int end, int[] array){
if(start < end){
// keep in mind that once we have the partition, pivot is already in the correct sorted position
int partition = partitionPoint(start,end,array); // find the correct position for the pivot
quickSort(start, partition-1, array); // recursively call the quick sort for the left had side of the pivot
quickSort(partition+1, end,array); // sort right hand side of the pivot
}
return array;
}
public static int partitionPoint(int start, int end, int[] array){
int pivot = array[end]; // choose the last element as pivot
int swapPosition = start;
for(int i=start; i<= end - 1; i++){
/**
* if value at i is less than pivot,
* swap the ith position with the swapPosition and incriment the swapPosition to next element.
*/
if(array[i] <= pivot){
swapElements(swapPosition, i, array);
swapPosition ++;
}
}
/* At the end swap the pivot with the swapposition.
This will move the pivot element to sorted position */
swapElements(swapPosition,end,array);
return swapPosition;
}
/**
* Swap the element in the position
*/
public static void swapElements(int position1, int position2, int[] array){
int temp = array[position1];
array[position1] = array[position2];
array[position2] = temp;
}
}
Let’s take a quick look at the time and space complexity of the Quicksort algorithm:
Quicksort works similar to the merge sort algorithm and recursively breaking the input in small sub problems. In the best case, it will split the input in two 2 equal half. Let’s see the time complexity for worst and best case.
Worst Case: In the worst case, partition might always pick the largest or smallest element from the input. In our example last element always picked as pivot element. This can happen if we sort the input array in increasing or decreasing order. In the worst case it’s possible for the complexity to get as high as O<(n^{2}.
TC(n) = TC(0) + TC(n-1) +(n)
Best Case: In the best case, the partition process always pick the middle element as Pivot. The best-case time and average case complexity of Quicksort is O(nLogn).
Quicksort is an in-place algorithm. This means, it does not need any extra array or data structure to store the intermediate results. This algorithm has a space complexity of O(n) where there are O(n) recursive calls (Worst case).
Both Quicksort and Mergesort algorithm have an average time complexity of O(n log n). but Quicksort is a preferred sorting algorithm for sorting Arrays. Here are some points which makes Quicksort a preferred sorting algorithm for Arrays.
Let’s see another variation of the Quicksort algorithm by selecting the first element as Pivot
public class QuckSortFirstElement{
public static void main(String[] args){
int[] input = {3,1,9,8,2,7,1,21,5,101,1};
quickSort(0, input.length-1, input);
for(int i=0; i< input.length; i++){
System.out.println(input[i]);
}
}
protected static void quickSort(int start, int end, int[] a){
if(start<end){
int index=partition(start,end,a);
quickSort(start,index-1,a);
quickSort(index+1,end,a);
}
return;
}
protected static int partition(int start, int end, int[] a){
int p = start;
int i = start;
int j= end;
while (i< j){
while(a[i]<= a[p] && i< end){
i++;
}
while(a[j]> a[p] && j > start){
j--;
}
if(i< j){
swap(i,j,a);
}
}
swap(j,p,a);
return j;
}
private static void swap(int p1, int p2, int[] a){
int temp = a[p1];
a[p1] = a[p2];
a[p2] = temp;
}
}
The worst case time complexity for the Quicksort is O(n^{2). }We can work on the randomization version of Quicksort algorithm where the expected time complexity is O(nLogn). Here is one of the variation of the randomized Quicksort algorithm.
Let’s see the code in action:
public class QuickSortRandom{
public static void main(String[] args){
int[] input = {3,1,11,8,21,2,6,12,103,3};
quickSort(0, input.length-1, input);
for(int i =0 ; i< input.length; i++){
System.out.println(input[i]);
}
}
public static void quickSort(int start, int end, int[] a){
if(start<end) {
int index = partition(start, end, a);
quickSort(start, index - 1, a);
quickSort(index + 1, end, a);
}
return;
}
protected static int partition(int start, int end, int[] a){
Random rand = new Random();
int median = rand.nextInt(end-start)+start;
int pIndex=start;
swap(median,end,a);
int pivot = end;
for(int i=start; i<= end-1; i++){
if(a[i] <= a[pivot]){
swap(i, pIndex, a);
pIndex++;
}
}
swap(pivot, pIndex,a);
return pIndex;
}
protected static void swap(int s1, int s2, int[] a){
int temp =a[s1];
a[s1] = a[s2];
a[s2] = temp;
}
}
In this article, we saw the Quicksort in Java. We discussed the different variations of the Quicksort algorithms. This is a very efficient algorithm and used in multiple places. At the end of our article, we learned the randomized version of Quicksort where the expected time complexity is O(nLogn) and not O(n^{2}) for most cases.
Hello!! Welcome to the Java Development Journal. We love to share our knowledge with our readers and love to build a thriving community.
Merge Sort in Java
Leave a Reply