Quick Sort Program in Java

In this article, we will write a quick sort program in Java. We will understand the partition procedure, the quicksort algorithm, and its worst-case and best-case analysis, and will write a quick sort program in Java.

Partition Procedure (Partition Algorithm)

Consider the array shown below.

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. We don’t care about 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 is based on the partitioning technique. We partition an unsorted array and we get an element at its sorted position. Then, we again send the array to the left of the partition index (the sorted position for the pivot element of the previous partition) to be partitioned and we send the array to the right of the partition index also to get partitioned. We 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 quicksort algorithm 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 is not a stable algorithm. This is because quicksort 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.

So, this is the complete discussion about the Quick Sort program in Java. We hope that you have understood the concepts and liked the discussion. We hope to see you again soon at PrepBytes.

Leave a Reply

Your email address will not be published. Required fields are marked *