Quick Sort in Java

Quick Sort in Java

In this article, we will explore Quick Sort in Java. We’ll understand how it works, analyze its performance, and implement it step by step using clear explanations and working code examples.

Sorting is a fundamental operation in computer science and plays a key role in improving the efficiency of searching and other operations. It is especially suitable for large datasets and often outperforms other sorting methods like Bubble Sort and Insertion Sort.

quick sort in java programming

What is Quick Sort in Java?

Quick Sort is a divide and conquer sorting algorithm. It works by selecting a pivot element from the array and partitioning the other elements into two sub arrays:

  • Elements less than the pivot go to the left.
  • Elements greater than the pivot go to the right.
  • Process is repeated recursively for both sub arrays until the entire array is sorted.

Quick Sort is an in-place sorting algorithm, which means it does not require extra space proportional to input size, making it memory-efficient.

how quick sort works
how quick sort works
  • Best and average cases occur when the pivot divides the array into two roughly equal parts.
  • Worst case occurs when the smallest or largest element is always chosen as the pivot, resulting in unbalanced partitions.

Quick Sort Algorithm:

Let’s break the Quick Sort algorithm into simple steps using an example array:

Example:
Array: [8, 4, 7, 3, 10, 2]

Step 1: Choose Pivot

Select a pivot element. Typically:

  • First element

  • Last element (we’ll use this)

  • Median or random (for better average case performance)

Let’s choose the last element as pivot → pivot = 2.

Step 2: Partitioning

Rearrange the array so that:

  • All elements less than pivot come before it.

  • All elements greater than pivot come after it.

We use two pointers:

  • i keeps track of the position where the smaller element should go.

  • j traverses from the start to one before the pivot.

Step 3: Recursively Apply to Subarrays

Apply the same steps to subarrays:

  • Left of pivot.

  • Right of pivot.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Implementation of Quick Sort in Java

Function Quick Sort Algorithm:

function quickSort(arr, low, high)
    if low < high:
        pivotIndex = partition(arr, low, high)
        quickSort(arr, low, pivotIndex - 1)
        quickSort(arr, pivotIndex + 1, high)

function partition(arr, low, high)
    pivot = arr[high]
    i = low - 1
    for j = low to high - 1:
        if arr[j] < pivot:
            i++
            swap arr[i] and arr[j]
    swap arr[i + 1] and arr[high]
    return i + 1
Quick Sort in Java
Quick Sort in Java

Java Code for Quick Sort Implementation

Run
public class QuickSortExample {

    // Function to perform Quick Sort
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // Partition the array and get the pivot index
            int pivotIndex = partition(arr, low, high);
            
            // Recursively sort elements before and after partition
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    // Function to partition the array
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // Choosing the last element as pivot
        int i = low - 1; // Index of smaller element

        for (int j = low; j < high; j++) {
            // If current element is smaller than the pivot
            if (arr[j] < pivot) {
                i++;
                // Swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // Swap the pivot element with the element at i+1 position
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1; // Return the partitioning index
    }

    // Utility function to print the array
    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

    // Main method to test the code
    public static void main(String[] args) {
        int[] array = {8, 4, 7, 3, 10, 2};

        System.out.println("Original Array:");
        printArray(array);

        quickSort(array, 0, array.length - 1);

        System.out.println("Sorted Array:");
        printArray(array);
    }
}
Quick Sort in Java continue
Quick Sort in Java continue

Conclusion

Quick Sort is one of the most powerful and widely used sorting algorithms due to its efficiency on large datasets and its in-place nature. While its worst case performance is O(n²), it can be optimized using better pivot selection strategies like randomized pivot or median of three.

  • Quick Sort is based on divide and conquer.
  • Partitioning is the key step.
  • It sorts in-place with O(log n) space complexity.
  • It is faster than bubble sort, insertion sort, and sometimes even merge sort for average cases.

Understanding Quick Sort not only helps in writing better sorting logic but also strengthens your fundamentals in recursion and algorithm optimization.

Quick sort in Java

FAQ's related to Quick Sort in Java

Answer:

Quick Sort is faster because it reduces the problem size significantly with each recursive call through partitioning. Unlike Bubble or Insertion Sort, which make multiple passes through the entire array, Quick Sort partitions the array into smaller subarrays and sorts them independently, leading to an average time complexity of O(n log n).

Answer:

Quick Sort performs worst when the pivot selection results in highly unbalanced partitions (e.g., already sorted arrays and always choosing the first or last element as pivot). This leads to O(n²) time complexity.

To avoid this:

  • Use a randomized pivot
  • Use the median-of-three technique to choose a better pivot

Answer:

  • No, Quick Sort is not stable by default. Stability means equal elements retain their original order after sorting. Since Quick Sort may swap distant elements during partitioning, it does not guarantee this behavior.
  • For applications requiring stability, consider Merge Sort or implement a custom stable version of Quick Sort.

Answer:

No extra array is used for sorting, so it’s considered in-place. However, it uses the call stack for recursion, which takes O(log n) space in the best and average cases, and O(n) in the worst case.

Answer:

Yes, Quick Sort can be adapted to sort objects (like arrays of custom classes) using comparators. You just need to define the comparison logic using either Comparable or Comparator interfaces to guide the partitioning process.

Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.

Data Structures and Algorithm Learn Sorting

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription