Here you will learn about quick sort in Java with program example.
As name suggested it is one of the fastest algorithms with average time complexity O(nlogn). It is also using divide and conquer strategy to sort as like merge sort. It has taken all advantages of merge sort and it has overcome the disadvantage of using auxiliary space also. It is popular because it is faster and also space efficient. But in worst case it is O(n^2) then also it is better than other sorting algorithms which exhibit O(n^2) time complexity.
Quick Sort Algorithm in Java
Step 1: it will choose an element as pivot element. There are many ways to select the pivot element. We can take first element as pivot element or last element, randomized element, middle element, etc.
Step 2: it will maintain two indexes one from left side and one form right side. First it will start search from left side for greater element than pivot then we will stop incrementing left index. Or else we will increment that left index.
Step 3: From right side we will search for lesser element than pivot. If we found lesser element than pivot then we will stop decrementing right index or else we will decrement right index.
Step 4: we should exchange elements so that all elements which are lesser than pivot should come to left side and elements that are greater than pivot should come to right side. Now we have greater element present at left side at left index and lesser element present at the right index. If we swap these 2 elements then they are at correct positions according to pivot.
Step 5: Again continue the same procedure until left index and right index cross each other means right index should be lesser than left index. Means all elements were placed right now right index position will be the pivot position. Pivot and the element present at right index should be swapped.
Step 6: Now array is dived into 2 parts. Elements which are present in the left side of pivot are one sub array and elements which are present at right side pivot is one array. It is division part. Recursively apply above procedure on sub arrays.
Step 7: the base condition for quick sort is same as merge sort. It will devide until sub array length is 1.
Quick Sort Example
First we will see how partition is going on by taking one element as pivot.
Here left index is indicated with low and right index is indicated with high. And low is incremented until it finds bigger one than pivot and high is remains same because it is lesser than pivot. We will swap them now.
Again same procedure will be continued until left and right indexes cross each other. And after crossing left and right indexes we should swap our pivot element with right index.
Now our list is divided into two sub arrays. Elements which are less than pivot came to left side and elements which are greater went to right side.
Now we will see how recursively quick sort will be called on array with simple example.
3 is taken as pivot element.
Array is partitioned by using pivot element. Now we call again quick sort algorithm on left sub array.
Again 2 is taken as pivot element in the left sub array.
Now again sub array also divided further again recursive call will done on remaining sub array. This is recursive process until sub array length is ‘1’.
Here entire left sub array of original problem is solved so it will call recursively on right sub array.
In right sub array 5 is first element so 5 will be pivot. According to that again right sub array will be partitioned.
Again recursive process until base condition found. At the end all values will get sorted.
Now we got an idea how quick sort is working. We will see program for quick sort algorithm.
Program for Quick Sort in Java
public class QuickSort{
public int partion(int arr[],int left, int right)
{
//take first element as a pivot
int pivot = arr[left];
// i is index that should trace the smallest elements than pivot.
// at last we will swap element at index i with pivot.
//means before ith index all elements should be less than pivot.
int i = left;
for(int j = left+1;j <= right;j++)
{
if(arr[j] < pivot)
{
i++; //small element found we should increment i.
swap(arr,i,j); //swap the elements so that small element will come to correct position.
}
}
// after loop ends before ith index all small elements were placed.
// now swap i index with the pivot.
swap(arr,i,left);
return i;
}
public void quicksort(int arr[],int low, int high)
{
if(low < high)
{
// dividing array with the pivot.
int p = partion(arr,low,high);
quicksort(arr,low,p-1);
quicksort(arr,p+1,high);
}
}
public void swap(int arr[],int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String args[])
{
int arr[] = {11,8,5,4,3,2,1,9};
QuickSort obj = new QuickSort();
System.out.print("elements before sorting\n");
for (int i = 0; i < arr.length;i++)
{
System.out.print(arr[i]+" ");
}
obj.quicksort(arr,0,7);
System.out.print("\nelements after sorting using quick sort\n");
for (int i = 0;i < arr.length;i++)
{
System.out.print(arr[i]+" ");
}
}
}
Output
elements before sorting
11 8 5 4 3 2 1 9
elements after sorting using quick sort
1 2 3 4 5 8 9 11
Performance
Quick Sort performance entirely based upon how we are choosing pivot element.
If pivot element divides array into two equal halves then it will exhibit good performance then its recursive function is:
T(n) = 2 * T(n/2) + O(n)
O(n) is for partitioning. If we solve this recursion equation we will get O(nlogn).
If pivot is not dividing array in proper way then performance decreases. We will see worst case now. Suppose in one pass we have taken largest element then it will divide n length array into n-1 elements one side ‘0’ . It is not a good division. If this happens in every pass then it will exhibit the worst case. Now recursive equation will be:
T(n) = T(n-1) + O(n).
If we solve this equation then we will get O(n^2).
Comment below if you doubts related to above program for quick sort in Java.