Quick Sort: An Efficient Divide-and-Conquer Sorting Algorithm¶

Quick Sort is an efficient sorting algorithm based on the divide-and-conquer principle. It selects a “pivot element” to partition the array into two parts: elements smaller than the pivot and elements larger than the pivot. It then recursively sorts these two parts. This approach efficiently handles large datasets with an average time complexity of O(n log n), making it one of the most commonly used sorting algorithms in practical applications.

Basic Steps of Quick Sort¶

Taking the array [6, 3, 8, 5, 2, 7] as an example, we demonstrate the Quick Sort process step by step:

1. Select the Pivot: Choose the rightmost element 7 as the pivot.
2. Partition: Traverse the array to move elements smaller than the pivot to the left and larger elements to the right. After partitioning, the array becomes [6, 3, 5, 2, 7, 8], with the pivot 7 at position 4 (0-indexed).
3. Recursive Sorting: Recursively sort the left subarray [6, 3, 5, 2] and the right subarray [8] (which is already sorted as its length is 1).
4. Process the Left Subarray: Repeat the steps for [6, 3, 5, 2]. Select the rightmost element 2 as the pivot. After partitioning, the array becomes [3, 5, 2, 6], with the pivot 2 at position 0. The left subarray is empty, and the right subarray [3, 5, 6] continues to be sorted recursively.
5. Final Result: After multiple recursive passes, the array is fully sorted: [2, 3, 5, 6, 7, 8].

Core Logic of the Partition Function¶

Partition is the critical step in Quick Sort, aiming to split the array into “elements less than the pivot” and “elements greater than the pivot,” returning the pivot’s final position. Using the rightmost element as the pivot, the process is as follows:

1. Define pivot = arr[right] (the pivot element).
2. Initialize a pointer i to the end of the “less-than-pivot region” (starting at left - 1).
3. Traverse the array from left to right - 1:
   - If the current element arr[j] <= pivot, increment i and swap arr[i] with arr[j] (expanding the “less-than-pivot region”).
4. After traversal, swap the pivot element pivot with arr[i + 1] (the end of the “less-than-pivot region” + 1). This ensures all elements to the pivot’s left are smaller, and all to the right are larger.

Java Code Implementation¶

Here is a complete Java implementation of Quick Sort, including the partition function and recursive sorting logic:

public class QuickSort {

    // Main Quick Sort method: recursively sorts the [left, right] interval of the array
    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int pivotIndex = partition(arr, left, right); // Partition and get pivot position
            quickSort(arr, left, pivotIndex - 1); // Recursively sort left subarray
            quickSort(arr, pivotIndex + 1, right); // Recursively sort right subarray
        }
    }

    // Partition function: selects the rightmost element as the pivot and returns its final position
    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[right]; // Pivot is the rightmost element
        int i = left - 1; // Pointer to the end of the "less-than-pivot" region

        for (int j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                i++; // Expand the "less-than-pivot" region
                // Swap current element with the element at i to include it in the region
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // Place the pivot in its final position (end of "less-than-pivot" region + 1)
        int temp = arr[i + 1];
        arr[i + 1] = arr[right];
        arr[right] = temp;

        return i + 1; // Return the pivot's index
    }

    // Test method to verify sorting correctness
    public static void main(String[] args) {
        int[] arr = {6, 3, 8, 5, 2, 7};
        System.out.println("Before sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

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

        System.out.println("\nAfter sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Code Execution Result¶

Running the above code produces the following output:

Before sorting:
6 3 8 5 2 7 
After sorting:
2 3 5 6 7 8 

Time and Space Complexity¶

• Time Complexity:
• Average case: O(n log n) (each partition splits the array into roughly equal parts, with recursion depth O(log n)).
• Worst case: O(n²) (e.g., sorted or reverse-sorted arrays, where each partition splits the array into 1 and n-1 parts, leading to recursion depth O(n)).
• Space Complexity: O(log n) on average (due to recursive call stack), with a worst-case O(n).

Summary¶

Quick Sort efficiently sorts arrays using divide-and-conquer, with partitioning as its core. Its strengths include high average efficiency and suitability for large datasets. However, it is an unstable sort (relative order of equal elements may change) and performs poorly in the worst case. Mastering Quick Sort not only builds understanding of divide-and-conquer algorithms but also serves as a foundation for learning more complex sorting techniques.