Quick Sort in Java

Last Updated: 06 October, 2024 🕓 5 Mins

Sorting is the process of arranging a list of unsorted data in a particular order, either ascending or descending. Sort algorithms play a very crucial role for organizing unsorted data and facilitating efficient searching, retrieval, and analysis.

Every sorting algorithm has a unique approach for sorting the data; these sorting algorithms are used according to the specific requirements of the problem, including data size, structure, and distribution, as well as time and space constraints.

In this tutorial, we are going to learn all about Quick Sort in Java.

What is Quick Sort?

Quick sort is an efficient and fast sorting algorithm used to sort a sorted list of elements.

Quick sort uses a divide and conquer strategy that means it attempts to separate the list of elements into two parts and then sort each part recursively. In quick sort, the partition of the list is performed based on the element called pivot. Here the pivot element is one of the elements in the list.

The list is divided into two partitions such that "all elements to the left of pivot are smaller than the pivot and all elements to the right of pivot are greater than or equal to the pivot.".

Example of Quick Sort in Java

  class QuickSortExample {
    
    // A utility function to swap two elements
    static void swap(int[] numberArray, int i, int j) {
      int temp = numberArray[i];
      numberArray[i] = numberArray[j];
      numberArray[j] = temp;
    }
  
    // This function takes last element as pivot,
    // places the pivot element at its correct position
    // in sorted array, and places all smaller to left
    // of pivot and all greater elements to right of pivot
    static int partition(int[] numberArray, int low, int high) {
      // Choosing the pivot
      int pivot = numberArray[high];
  
      // Index of smaller element and indicates
      // the right position of pivot found so far
      int i = (low - 1);
  
      for (int j = low; j <= high - 1; j++) {
  
        // If current element is smaller than the pivot
        if (numberArray[j] < pivot) {
  
          // Increment index by 1
          i++;
          swap(numberArray, i, j);
        }
      }
      swap(numberArray, i + 1, high);
      return (i + 1);
    }
  
    // Function to performs the quick sort
    // numberArray[] --> Array to be sorted,
    // low --> Starting index of array,
    // high --> Ending index of array
    static void quickSort(int[] numberArray, int low, int high) {
      if (low < high) {
  
        // the variable 'part' is a partitioning index, array[p]
        // is now at right place
        int part = partition(numberArray, low, high);
  
        // Separately sort elements before
        // partition and after partition
        quickSort(numberArray, low, part - 1);
        quickSort(numberArray, part + 1, high);
      }
    }
  
    // Function to print an array
    static void printArray(int[] array) {
      for (int i = 0; i < array.length; i++) {
        System.out.print(array[i] + " ");
      }
    }
  
    public static void main(String[] args) {
      // Creates an array
      int[] array = { 40, 70, 90, 20, 80, 100, 60, 10, 30, 50 };
      int length = array.length;
  
      // Calling a function to sort an array
      quickSort(array, 0, length - 1);
  
      System.out.println("Sorted Array:");
      printArray(array);
    }
  }