Sorting is a fundamental operation in computer science, and QuickSort is one of the most popular and efficient sorting algorithms. In this blog post, we’ll look at a Java implementation of QuickSort, explain how it works, break down its steps with a sample output, and even visualize its working.

What is QuickSort?

QuickSort is a highly efficient, comparison-based, divide-and-conquer sorting algorithm. It was developed by Tony Hoare in 1959 and is widely used due to its performance on average-case scenarios.

How QuickSort Works:

1. Divide: Select a pivot element from the array. Rearrange the array such that all elements less than the pivot go to its left, and all elements greater than the pivot go to its right.
2. Conquer: Recursively apply the above step to the left and right subarrays.
3. Combine: Since the array is sorted in-place, there’s no need for a combine step as in merge sort.

Java Code: QuickSort Implementation

package quicksort;
import java.io.*;

public class QuickSort {

    // Array to be sorted
    static protected int a[];

    public static void main(String args[]) throws IOException {
        BufferedReader obj = new BufferedReader(new InputStreamReader(System.in));

        // Read the number of elements
        System.out.println("Enter number of elements:");
        int n = Integer.parseInt(obj.readLine());
        a = new int[n];

        // Read array elements from the user
        System.out.println("Enter elements");
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(obj.readLine());
        }

        // Call QuickSort
        quicksort(a, 0, n - 1);

        // Print sorted array
        System.out.println("Sorted List:");
        for (int j = 0; j < n; j++) {
            System.out.print(a[j] + " ");
        }
    }

    // Recursive quicksort function
    static void quicksort(int t[], int p, int r) {
        if (p < r) {
            // Partition the array and get the pivot index
            int q = partition(t, p, r);
            // Recursively sort the elements before and after the partition
            quicksort(t, p, q - 1);
            quicksort(t, q + 1, r);
        }
    }

    // Partition function
    static int partition(int ta[], int l, int h) {
        int x = ta[h]; // pivot element
        int i = l - 1;

        // Rearranging elements based on pivot
        for (int j = l; j <= h - 1; j++) {
            if (ta[j] <= x) {
                i = i + 1;
                // Swap ta[i] and ta[j]
                int temp = ta[j];
                ta[j] = ta[i];
                ta[i] = temp;
            }
        }

        // Place the pivot element at the correct position
        int temp2 = ta[i + 1];
        ta[i + 1] = ta[h];
        ta[h] = temp2;

        a = ta; // update the static array reference
        return (i + 1); // return the partition index
    }
}

Sample Output

Enter number of elements:
6
Enter elements
15
34
26
67
95
24
Sorted List:
15 24 26 34 67 95

Output Explanation

Let’s break down the sample run in detail:

User Input:

The user enters 6 elements:

[15, 34, 26, 67, 95, 24]

Step-by-Step QuickSort Execution:

1. First Partition Call (entire array):
   • Pivot chosen: 24 (last element)
   • Rearrangement:
     • 15 is less than 24 → kept on the left
     • 34, 26, 67, and 95 are all greater than 24 → skipped
   • Swap 24 with first element greater than it → placed after 15
   • Result: [15, 24, 26, 67, 95, 34]
2. Recursive Call on Left Subarray [15]:
   • Single element → already sorted.
3. Recursive Call on Right Subarray [26, 67, 95, 34]:
   • Pivot: 34
   • 26 < 34 → kept left
   • 67, 95 > 34 → skipped
   • Swap 34 into correct position
   • Result: [15, 24, 26, 34, 95, 67]
4. Final Step: [95, 67] sorted using pivot 67
   • 95 > 67 → no change
   • 67 swapped into correct position
   • Final sorted array: [15, 24, 26, 34, 67, 95]

Why QuickSort is used?

• Efficient: Average time complexity is O(n log n).
• In-place: Does not require additional memory like MergeSort.
• Widely used: Commonly used in language libraries and frameworks due to its speed and efficiency.

Time Complexity:

• Best/Average Case: O(n log n)
• Worst Case: O(n²) — when the pivot is always the smallest or largest element (can be avoided with good pivot strategies).