This tutorial shows how to write Quick sort program in Java. Quick sort is also a "divide and conquer algorithm" like Merge sort.
Quick Sort Algorithm
Quick sort works as follows-
- Chose an element as pivot and then partition all the elements around that pivot.
- All the elements having value less than the pivot come before the pivot.
- All the elements having value higher than the pivot come after the pivot.
Once the elements are partitioned around pivot you get two sub-arrays. One on the left of the pivot having values smaller than the pivot and another on the right of the pivot having values greater than the pivot. Steps 1-3 are executed recursively for these 2 sub-arrays.
One of the decision you have to make while implementing Quick sort is what value should be chosen as pivot, options are-
- First element as pivot.
- Last element as pivot (Quick sort implementation in this post uses this approach)
- Middle element as pivot.
- Median of the items being sorted.
For example suppose the input arrays is- [40, 62, 49, 10, 39, 65, 75, 32, 53, 46]
The starting point for partition process is explained using the below image.
From left move towards right searching for an element greater than pivot value. From the right move towards left searching for an element smaller than pivot. Once such elements are found swap those elements. In our example such elements are 62 (from left) and 32 (from right) on swapping them array becomes- [40, 32, 49, 10, 39, 65, 75, 62, 53, 46]
Moving on again such elements are found 49 (from left) and 39 (from right) on swapping them array becomes- [40, 32, 39, 10, 49, 65, 75, 62, 53, 46]. At this time left is pointing at 39 and right is pointing at 49.
Once the left becomes greater than right, which happens in our example when left starts pointing at 49 and right starts pointing at 39, swap left with the pivot which gives us two partitions and pivot at its final position- [40, 32, 39, 10, 46, 65, 75, 62, 53, 49]
Process is repeated again with the partitioned arrays.
Quick Sort Java program
public class QuickSort {
public static void main(String[] args) {
int[] arr = {108, 52, 23, 32, 3, 56, 87, 62, 37, 91, 34, 78};
System.out.println("Original array- " + Arrays.toString(arr));
quickSort(arr, 0, arr.length-1);
System.out.println("Sorted array after quick sort- " + Arrays.toString(arr));
}
private static void quickSort(int[] arr, int lower, int upper){
// base case
if(upper - lower <= 0){
return;
}else{
int partition = partition(arr, lower, upper);
// recursive call with smaller values partition
quickSort(arr, lower, partition-1);
// recursive call with higher values partition
quickSort(arr, partition+1, upper);
}
}
private static int partition(int[] arr, int lower, int upper){
int pivot = arr[upper];
int left = lower - 1;
int right = upper;
while(left <= right) {
// find an element greater than pivot
// starting from the left side
while(arr[++left] < pivot);
// find an element smaller than pivot
// starting from the right side
while(right > 0 && arr[--right] > pivot);
// break out of loop whenever left is greater than right
if(left >= right)
break;
else{
swap(arr, left, right);
}
}
// to get pivot at its proper place
swap(arr, left, upper);
return left;
}
private static void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
Output
Original array- [108, 52, 23, 32, 3, 56, 87, 62, 37, 91, 34, 78] Sorted array after quick sort- [3, 23, 32, 34, 37, 52, 56, 62, 78, 87, 91, 108]
Quick sort time and space complexity
Average and best case time complexity of quick sort is O(n*logn). In worst case, when pivot value doesn’t partition elements properly, time complexity can be O(n2).
When implemented recursively extra space for recursive call method stacks is required so the worst case space complexity of Quick sort is O(n).
That's all for the topic Quick Sort Java Program. If something is missing or you have something to share about the topic please write a comment.
You may also like
No comments:
Post a Comment