Quick Sort Program in Java

In this post we’ll see how to write quick sort program in Java. Quick sort is considered the fastest in-memory sorting technique in most of the situations. Just like Merge sort, Quick sort is also a divide and conquer algorithm which works on the idea of partitioning the large list into smaller lists around a chosen value (pivot) so that all the smaller values than the pivot are on the left and all the higher values than the pivot are on the right. Quick sort then recursively sort the list with smaller values and the list with higher values by further partitioning it around pivot.

How does quick sort work

Steps for implementing the quick sort are as follows-

Chose a pivot value (it must be one of the element from the list that is sorted).
Partition the list in such a way that all the elements having value less than the pivot come before the pivot (smaller element list) and all the elements having value higher than the pivot come after the pivot (higher element list). Once this partitioning is done pivot value is at its final position.
Recursively call the above steps separately for the smaller element list and for the higher element list.

You can pick any random value as the pivot while implementing quick sort-

First element in the list as pivot.
Last element in the list as pivot (Quick sort implementation given here uses this approach)
Middle element as pivot.
Median of the items being sorted.

Quick Sort Java program

First let’s see the Java program for quick sort and then we’ll try to understand what is happening with the help of the program code.

public class QuickSort {
  public static void main(String[] args) {
    int[] numberArr = {47, 65, 52, 10, 43, 67, 80, 34, 55, 48};
    QuickSort qs = new QuickSort();
    qs.quickSortRecursive(numberArr, 0, numberArr.length-1);
    System.out.println("Sorted array after quick sort- ");
    for(int num : numberArr){
      System.out.print(num + " ");
    }
  }
    
  private void quickSortRecursive(int[] numberArr, int lower, int upper){
    if(upper - lower <= 0){
      return;
    }else{
      int partition = partition(numberArr, lower, upper);
      // calling method again with smaller values
      quickSortRecursive(numberArr, lower, partition-1);
      // calling method again with higher values
      quickSortRecursive(numberArr, partition+1, upper);
    }
  }
    
  private int partition(int[] numberArr, int lower, int upper){
    int pivot = numberArr[upper];
    int left = lower - 1;
    int right = upper;
    while(true){
      // find an element greater than pivot 
      // starting from the beginning
      while(numberArr[++left] < pivot);
      // find an element smaller than pivot
      // starting from the end
      while(right > 0 && numberArr[--right] > pivot);
      if(left >= right){
        break;
      }else{
        swap(numberArr, left, right);
      }
    }
    swap(numberArr, left, upper);
    return left;
  }
    
  private void swap(int[] numberArr, int i, int j){
    int temp = numberArr[i];
    numberArr[i] = numberArr[j];
    numberArr[j] = temp;
  }
}

Output

Sorted array after quick sort- 
10 34 43 47 48 52 55 65 67 80

Understanding the quick sort program

In the program there is a quickSortRecursive method which is called recursively with the two arrays; one containing the elements smaller than the pivot and another containing the elements greater than the pivot. For partitioning the elements there is a partition method.

Initially when the partitioning starts array is as depicted in the given image.

For the swapping of the elements we’ll start at both ends of the array. From the left move towards right looking for an element greater than pivot value. From the right move towards left looking for an element smaller than pivot.

These while loops are doing it in the code.

while(numberArr[++left] < pivot);


while(right > 0 && numberArr[--right] > pivot);

If you find such numbers before the break condition (left >= right) you swap those elements so that smaller numbers are on one side of the pivot and greater on the other side.

From the array you can see that starting from the left 65 > 48 and from the right 34 < 48 so these numbers are swapped. Continuing from the next index at the left side 52 > 48 and from the right 43 < 48 so these numbers are swapped. At this point your array would look like as given below, with left index at 43 and right at 52-

47 34 43 10 52 67 80 65 55 48

From here continuing from the next index at the left side again 52 > 48 and from the right 10 < 48 but at this point (left >= right) so control comes out of the loop and swapping for the pivot is done.

swap(numberArr, left, upper);

Swap the value at left index with the pivot value which brings pivot at its final position and gives two sub arrays.

Then the same process is repeated with the two sub-arrays.

Performance of quick sort

Average time complexity of quick sort is O(N*logN). In worst case it can be O(N²).

Every recursive call will have its own stack space so space complexity of quick sort is O(N).

That's all for this topic Quick Sort Program in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Tech Tutorials

Saturday, April 9, 2022