Quick Sort Program in Java

Last Updated on April 17, 2023 by Prepbytes

Quick Sort program in Java has been introduced because it is an efficient sorting algorithm that can quickly sort large datasets. It has a time complexity of O(n log n) and is widely used in many programming applications.

Introduction to Quick Sort Program in Java

Quick Sort program in Java is a fast and efficient sorting algorithm in Java, which works by recursively dividing and sorting sub-arrays. It selects a pivot element and then partitions the array based on whether elements are greater or lesser than the pivot.

Quick Sort Algorithm in Java

Here,is the quick sort algorithm in Java. Consider the array shown below.

Here, We have to partition the given array. Partitioning an array around a value pivot means that we arrange the array in such a way that the pivot is in its sorted position. And we don’t consider the rest of the array. The pivot element will be at a position in which it will be if we sort an array. This means that the elements before the pivot element i.e. the elements to the left of the pivot will be smaller than the pivot and the elements after the pivot element i.e. the elements to the right of the pivot element will be larger than the pivot.

For instance, consider the array shown below.

Here 10 is at its sorted position. The elements to the left of the value 10 are smaller than 10 and the elements to the right of element 10 are larger than 10. Their respective order does not matter i.e. we can see that the left part is not sorted and the right part is also not sorted itself.

So, let’s come back to our example, we have the initial condition as shown below.

The pivot value here is 5. We have assumed that the pivot will always be the last element of the array. The partitioning technique in which the last element of the array is always chosen as the pivot is called the Lomuto partition.

There are 2 pointers l and r at the top of the first element. The ticks below every element represent that all the elements are unexplored at the current moment. See, to partition the array, we have to divide the array into 2 regions, one where the elements will be smaller than the pivot and the other where the elements will be larger than the pivot. However, currently, all the elements are divided into 3 regions.

The 3 regions are; greater than the pivot, less than the pivot, and unexplored elements. Currently, there are no elements in the first 2 regions and all the elements are in the unexplored region. As we go on and move the pointers l and r, we will keep on adding the elements to one of the first 2 regions.

If the number of elements in the array is N, the following image shows the ranges of all the 3 regions.

So, we have to work according to this. Let’s see the first step shown below.

We were at element 7 and pivot = last element = 5. So, 7 is greater than 5. We know that the region for the elements greater than the pivot is from l to r-1. So, l=0 which is correct as 7 is at index 0. However, r-1=0-1=-1. This is incorrect. So, to validate the range l to r-1, we need to move r one step forward. So, we do r++.

Now r is at index 1. So, we can see that the range for the elements greater than the pivot has been satisfied. Also, the other 2 ranges have automatically been validated as the unexplored region is now from index 1 onwards and less than equal to pivot is currently a non-existing region after exploring just 1 element.

With this, we have also come to the conclusion that if arr[r] > pivot, we do r++.

Next, we have element 9. So, perform the same operation and r will be at index 1. (Do it yourself to get the concept clearly).

Now, we are at index 2 i.e. element 4.

As shown above, the previous 2 elements have now come under the >pivot region. Element 4 is, however, less than the pivot i.e. 5. So, to validate the ranges mentioned above, we will swap the elements at the l and r indices and increment both l and r as shown below.

Now, we can see that the ranges are validated automatically. So, we have come to the conclusion that if arr[r] < pivot, we swap arr[l] and arr[r] and do l++ and r++.
So, you can follow the same steps yourself for the remaining array. The array after r goes out of bound is shown below.

So, we can see that the array has been partitioned. Throughout the partition procedure, the left pointer or l denotes the first element of the >pivot region and the right pointer or r denotes the first element of the unexplored region.

Now that we have understood the complete partition procedure, let us write the code for the same.

Partition Procedure Program in Java

import java.util.*;

public class Main {
    
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    public static void partition(int[] arr, int pivot) {
        int l = 0;
        int r = 0;
        
        while(r < arr.length) {
            if(arr[r] > pivot) r++;
            else {
                swap(arr,l,r);
                l++;
                r++;
            }
        }
    }
    
    public static void display(int[] arr) {
        
        for(int i=0;i<arr.length;i++) {
            System.out.print(arr[i] + " ");
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {7,9,4,8,3,6,2,5};
        partition(arr,5);
        display(arr);
    }
}

Time Complexity of Partition Procedure: The time complexity of the partition procedure is O(N) as we have to traverse the entire array.

Space Complexity of Partition Procedure: The auxiliary space is O(1) as we have not used any extra space.

So, now that we have understood the partition procedure completely, we can now write the quick sort program in Java.

Quick Sort Program in Java

The quick sort algorithm in Java is based on the partitioning technique. The partition of an unsorted array is that we get an element at its sorted position. And then, we send the array from the left of the partition index (the sorted position for the pivot element of the previous partition) to be partitioned and then we send the array to the right of the partition index also to get partitioned. We need to do this recursively till the array gets sorted.

For instance, consider the array shown below.

After partitioning the array for the first time, we get the pivot at index 2. Then, we will send the 2 arrays for partition. The recursion tree for the same is shown below.

The partitioning technique that we have used in the above quicksort algorithm is called Lomuto’s partition. In Lomuto’s partition technique, both the pointers left and right start from index 0 and move in the same direction.

There is another popular partitioning technique called Hoare’s partition. In Hoare’s partition, the left and right index start from the start and the end index of the array respectively, and move in opposite directions i.e. towards each other.

Hoare’s partition can be considered slightly optimized than Lomuto’s partition because it caused 3 times fewer swaps. However, the average and the worst-case time complexity of the quicksort algorithm remain the same using any of the 2 partition techniques.

Now that we have understood the quicksort algorithm, let us write the quick sort program in Java.

Quick Sort Program in Java

import java.util.*;

public class Main {
    
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
     public static void quickSort(int[] arr, int lo, int hi) {
    //write your code here
    
    if(lo > hi) return;
    
    int pivot = arr[hi];
    int partitionIndex = partition(arr,pivot,lo,hi);
    
    quickSort(arr,lo,partitionIndex -1);
    quickSort(arr,partitionIndex + 1,hi);
  }

  public static int partition(int[] arr, int pivot, int lo, int hi) {
    int i = lo, j = lo;
    while (i <= hi) {
      if (arr[i] <= pivot) {
        swap(arr, i, j);
        i++;
        j++;
      } else {
        i++;
      }
    }
    return (j - 1);
  }
    
    public static void display(int[] arr) {
        
        for(int i=0;i<arr.length;i++) {
            System.out.print(arr[i] + " ");
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {7,9,4,8,3,6,2,5};
        quickSort(arr,0,arr.length-1);
        display(arr);
    }
}

Time Complexity of Quick Sort Program in Java

The average case time complexity of the quick sort algorithm in java is O(NlogN) where N is the number of elements in the array. This can be proved by solving the recurrence relation of the quicksort algorithm which is as follows: T(N) = T(N/2) + O(N). This T(N/2) term came because after partition, the array gets divided into 2 halves almost (in the average case, we consider it to be half) and we solve each half separately. The O(N) term is because of the partition procedure that takes O(N) time.

The worst-case time complexity of quicksort is O(N2). This happens due to the formation of the recurrence relation: T(N) = T(N-1) + O(N). This T(N-1) term occurs when the partition takes place at the end of the array i.e. the partition index is either 0 or N-1.

So, the worst case is partitioning happening at the end of the array and the worst-case time complexity is O(N2).
The average and the best-case is partitioning happening at the middle of the array and the best-case and the average-case time complexity is O(nlogn).

The following image shows the solution of the recurrence relation: T(N) = T(N/2) + O(N).

The below image shows the solution of the recurrence relation: T(N) = T(N-1) + O(N).

Space Complexity of the Quick Sort Program in Java:
The auxiliary space is O(1) as we have not used any extra space. However, the recursion space is O(N) in the worst case.

Is QuickSort Stable?

No, quicksort in java is not a stable algorithm. This is because quicksort in java depends on the partition algorithm and partition algorithm is not stable. To understand what a stable algorithm means, have a look at the image shown below.

So, if the order of the equal elements is maintained after sorting, the algorithm is said to be stable. However, quicksort is not stable as the order after partitioning might or might not remain the same.

Conclusion
Quick sort algorithm in java is an efficient sorting algorithm that works by recursive partitioning and sorting sub-arrays. We can implement it in Java using a combination of recursive functions and a partitioning algorithm to sort large datasets efficiently.

Frequently Asked Questions(FAQs)

Q1. What is Quick Sort program in java?
Ans: Quick Sort program in java is an efficient sorting algorithm that sorts an array or a list by partitioning it into smaller sub-arrays or sub-lists, sorting them recursively, and then merging them back together.

Q2. What is the time complexity of the Quick Sort algorithm in java?
Ans: The worst-case time complexity of Quick Sort algorithm in java is O(n^2), but on average, its time complexity is O(n log n), which makes it one of the most efficient sorting algorithms.

Q3. What is the Quick Sort algorithm in java?
Ans: Quick Sort algorithm in java is a divide-and-conquer sorting algorithm that works by selecting a pivot element from the array, partitioning the array into two sub-arrays or sub-lists, one with elements less than the pivot and the other with elements greater than or equal to the pivot, and then recursively sorting these sub-arrays or sub-lists.

Q4. How does Quick Sort program in java works?
Ans: Quick Sort program in java works by selecting a pivot element from the array, partitioning the array into two sub-arrays or sub-lists, one with elements less than the pivot and the other with elements greater than or equal to the pivot, and then recursively sorting these sub-arrays or sub-lists.