Quick Sort in Java

Q: How does quick sort work?

Quick sort picks a pivot, partitions the array so that smaller elements are on the left and larger ones on the right, and then sorts the two parts recursively. The pivot ends up in its final position after partitioning.

Q: Write quick sort in Java using the Lomuto partition.

Java example: import java.util.Arrays; public class QuickSort { static void quickSort(int[] arr, int low, int high) { if (low < high) { int p = partition(arr, low, high); quickSort(arr, low, p - 1); quickSort(arr, p + 1, high); } } static int partition(int[] arr, int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] < pivot) { i++; swap(arr, i, j); } } swap(arr, i + 1, high); // place the pivot after the smaller elements return i + 1; } static void swap(int[] arr, int a, int b) { int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } public st

Q: What is the time complexity of quick sort?

Average and best case: O(n log n). Worst case: O(n 2 ), when the pivot is always the smallest or largest element, for example the last element of an already sorted array. Space: O(log n) on average for the recursion stack.

Q: How can you avoid the O(n²) worst case?

Choose a better pivot: a random element, or the median of three (first, middle and last). Recursing into the smaller part first and looping over the larger part also limits the stack depth to O(log n).

Q: Why is quick sort often faster than merge sort in practice?

It sorts in place, so it needs no extra array, and it accesses memory sequentially, which suits CPU caches. Its inner loop is also very simple. That is why Java's Arrays.sort for primitive arrays uses a dual-pivot quick sort.

Q: What is the difference between the Lomuto and Hoare partition schemes?

Lomuto uses the last element as pivot and one index; it is simpler but does more swaps. Hoare uses two indexes moving toward each other; it does about three times fewer swaps on average and handles many equal elements better.

Quick Sort in Java

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.".

The quick sort algorithm was invented by C. A. R. Hoare.

Example of Quick Sort in Java

QuickSortExample.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);
  }
}

Output

Sorted Array:

10 20 30 40 50 60 70 80 90 100

Frequently Asked Questions (FAQ)

Q1. How does quick sort work?

Quick sort picks a pivot, partitions the array so that smaller elements are on the left and larger ones on the right, and then sorts the two parts recursively. The pivot ends up in its final position after partitioning.

Q2. Write quick sort in Java using the Lomuto partition.

QuickSort.java

import java.util.Arrays;

public class QuickSort {

    static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int p = partition(arr, low, high);
            quickSort(arr, low, p - 1);
            quickSort(arr, p + 1, high);
        }
    }

    static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);         // place the pivot after the smaller elements
        return i + 1;
    }

    static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));   // [1, 5, 7, 8, 9, 10]
    }
}

Q3. What is the time complexity of quick sort?

Average and best case: O(n log n).
Worst case: O(n²), when the pivot is always the smallest or largest element, for example the last element of an already sorted array.
Space: O(log n) on average for the recursion stack.

Q4. How can you avoid the O(n²) worst case?

Choose a better pivot: a random element, or the median of three (first, middle and last). Recursing into the smaller part first and looping over the larger part also limits the stack depth to O(log n).

RandomPivot.java

import java.util.concurrent.ThreadLocalRandom;

static void randomizePivot(int[] arr, int low, int high) {
    int r = ThreadLocalRandom.current().nextInt(low, high + 1);
    int temp = arr[r];
    arr[r] = arr[high];
    arr[high] = temp;               // the random element becomes the pivot at 'high'
}

Q5. Is quick sort stable?

No. Partitioning swaps elements over long distances, so equal elements can change their relative order.

Q6. Why is quick sort often faster than merge sort in practice?

It sorts in place, so it needs no extra array, and it accesses memory sequentially, which suits CPU caches. Its inner loop is also very simple. That is why Java's Arrays.sort for primitive arrays uses a dual-pivot quick sort.

Q7. What is the difference between the Lomuto and Hoare partition schemes?

Lomuto uses the last element as pivot and one index; it is simpler but does more swaps. Hoare uses two indexes moving toward each other; it does about three times fewer swaps on average and handles many equal elements better.

Q8. Write a Java method that finds the k-th smallest element using quick select.

QuickSelect.java

static int quickSelect(int[] arr, int k) {        // k is 0-based
    int low = 0, high = arr.length - 1;
    while (low <= high) {
        int pivot = arr[high];
        int i = low;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
                i++;
            }
        }
        int t = arr[i]; arr[i] = arr[high]; arr[high] = t;
        if (i == k) return arr[i];
        if (i < k) low = i + 1; else high = i - 1;
    }
    return -1;
}

Only one side is processed after each partition, so the average time is O(n).

Q9. What happens with many duplicate values?

With a two-way partition, many equal values can make the parts very unbalanced, degrading towards O(n²). A three-way partition (less than, equal to, greater than the pivot) groups all equal values together and skips them in the recursion.

Q10. When should you not use quick sort?

When you need a stable sort, a guaranteed worst case, or you are sorting linked lists. Merge sort or TimSort is better there.

Was this tutorial helpful?

Help Us Improve

What is Quick Sort?

Example of Quick Sort in Java

Frequently Asked Questions (FAQ)