Quick Sort in Java

1. Introduction

Quick Sort is a widely-used, efficient, and comparison-based divide-and-conquer sorting algorithm. It was developed by Tony Hoare in 1959.

Quick Sort works by selecting a pivot element from the array, partitioning the remaining elements into two sub-arrays:

Elements less than or equal to the pivot go to the left
Elements greater than the pivot go to the right

The same process is then recursively applied to the sub-arrays.

2. Step-by-Step Explanation of the Algorithm

Let’s break down Quick Sort with clarity.

Choose a pivot element
- Common choices: First element, last element, middle element, or a random one.
Partition the array
- Rearrange elements so that all items smaller than the pivot come before it, and all larger ones come after.
Recursively apply the same steps to the sub-arrays formed by partitioning.
Base case: When the sub-array has one or no elements, it is already sorted.

3. Implementation

public class QuickSort {

    // Main function to initiate the sort
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // Find the pivot index after partition
            int pivotIndex = partition(arr, low, high);
            
            // Recursively sort elements before and after partition
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    // Partitioning method
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];  // Choose the last element as pivot
        int i = low - 1; // Index of smaller element

        for (int j = low; j < high; j++) {
            // If current element is <= pivot
            if (arr[j] <= pivot) {
                i++;

                // Swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // Swap arr[i + 1] and pivot
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

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

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

    // Driver method
    public static void main(String[] args) {
        int[] arr = { 10, 7, 8, 9, 1, 5 };
        System.out.println("Original Array:");
        printArray(arr);

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

        System.out.println("Sorted Array:");
        printArray(arr);
    }
}

4. Explaination of the partition step

4.1 Purpose of the Partition Step

The partition step is the heart of Quick Sort. Its goal is to:

Choose a pivot element.
Reorder the array so that:
- All elements less than or equal to the pivot are placed to the left.
- All elements greater than the pivot are placed to the right.
Return the final index of the pivot, which is now in its correct sorted position.

4.2 General Idea of Partition Algorithm

Choose a pivot (commonly the last element).
Initialize an index i = low - 1. It will mark the boundary for elements less than or equal to the pivot.
Iterate j from low to high - 1:
- If arr[j] <= pivot:
  - Increment i
  - Swap arr[i] with arr[j]
Finally, place the pivot in its correct position by swapping arr[i+1] with arr[high].

4.3 Step-by-Step Example with Visual Representation

Let’s walk through an example.

Input Array:

int[] arr = { 10, 80, 30, 90, 40, 50, 70 };

Parameters:

low = 0
high = 6
So pivot = arr[6] = 70

Initial Setup:

Array:        [10, 80, 30, 90, 40, 50, 70]
Indexes:       0   1   2   3   4   5   6
i = -1
pivot = 70 (arr[6])

Step-by-Step Execution:

j = 0

arr[0] = 10 <= 70 → yes
Increment i = 0
Swap arr[0] with arr[0] → no change

i=0
[10, 80, 30, 90, 40, 50, 70]

j = 1

arr[1] = 80 > 70 → skip

i=0
[10, 80, 30, 90, 40, 50, 70]

j = 2

arr[2] = 30 <= 70 → yes
Increment i = 1
Swap arr[1] with arr[2]

i=1
[10, 30, 80, 90, 40, 50, 70]

j = 3

arr[3] = 90 > 70 → skip

i=1
[10, 30, 80, 90, 40, 50, 70]

j = 4

arr[4] = 40 <= 70 → yes
Increment i = 2
Swap arr[2] with arr[4]

i=2
[10, 30, 40, 90, 80, 50, 70]

j = 5

arr[5] = 50 <= 70 → yes
Increment i = 3
Swap arr[3] with arr[5]

i=3
[10, 30, 40, 50, 80, 90, 70]

After Loop Ends:

i = 3
Swap arr[i+1] with arr[high] → Swap arr[4] with arr[6] (pivot)

[10, 30, 40, 50, 70, 90, 80]

Pivot (70) is now at index 4, and everything to the left of it is <= 70, everything to the right is > 70.

5. Visual Summary of Each Step

Step 0: Initial
         10  80  30  90  40  50  70
         ^                   ^     pivot = 70
        low                 high

Step 1: arr[0] = 10 <= 70 → swap with itself
         10  80  30  90  40  50  70
         ↑
         i

Step 2: arr[1] = 80 > 70 → skip
         i stays at 0

Step 3: arr[2] = 30 <= 70 → swap arr[1] and arr[2]
         10  30  80  90  40  50  70
             ↑
             i

Step 4: arr[3] = 90 > 70 → skip

Step 5: arr[4] = 40 <= 70 → swap arr[2] and arr[4]
         10  30  40  90  80  50  70
                 ↑
                 i

Step 6: arr[5] = 50 <= 70 → swap arr[3] and arr[5]
         10  30  40  50  80  90  70
                     ↑
                     i

Final: swap arr[4] with pivot (arr[6])
         10  30  40  50  70  90  80
                          ↑
                       pivotIndex = 4

6. Time Complexity

Case	Time Complexity
Best	O(n log n) — when partition splits are balanced
Average	O(n log n)
Worst	O(n²) — when the smallest or largest element is always picked as pivot (unbalanced partitions)

Note: Worst case is rare in practice if pivot is chosen well (e.g., using randomized or median-of-three approach)

7. Space Complexity

O(log n) due to recursive calls on the stack (for balanced partitions)
In-place sorting: No extra array used

8. Advantages of Quick Sort

Faster in practice than other O(n log n) algorithms like Merge Sort due to better cache performance.
In-place sort (no extra memory needed like merge sort).
Tail recursion optimizations are possible.

9. Disadvantages of Quick Sort

Not stable (relative ordering of equal elements not preserved).
Worst-case time is O(n²), though can be avoided with better pivot strategies.
Recursive implementation can lead to stack overflow on very large datasets.

10. When to Use Quick Sort

When in-place sorting is required and stability is not a concern.
When average-case performance is more critical than worst-case.
When performance is paramount and data fits in memory.