Understanding QuickSort Algorithm in Java

QuickSort is a widely used sorting algorithm known for its efficiency and simplicity. Developed by Tony Hoare in 1960, QuickSort employs a divide-and-conquer strategy to efficiently sort an array or list of elements. This article explores a Java implementation of the QuickSort algorithm, providing a step-by-step explanation of its key components.

Code:

package sorting;

public class QuickSort {
    public static void main(String[] args) {
        int[] nums = { 1, 6, 5, 8, 2, 9, 3, 4, 7 };
        quickSort(nums, 0, nums.length - 1);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
    }

    public static void quickSort(int[] nums, int low, int high) {
        if (low < high) {
            // Partition the array
            int pivot = partition(nums, low, high);
            // Sort the left subarray
            quickSort(nums, low, pivot - 1);
            // Sort the right subarray
            quickSort(nums, pivot + 1, high);
        }
    }

    public static int partition(int[] nums, int low, int high) {
        // Choose the rightmost element as the pivot
        int pivot = nums[high];
        // Index indicating the first element that's greater than the pivot
        int i = low - 1;
        // Traverse through the array
        for (int j = low; j < high; j++) {
            // If the current element is smaller than or equal to the pivot
            if (nums[j] <= pivot) {
                // Increment the index of smaller elements
                i++;
                // Swap the current element with the element at the index
                // of smaller elements
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        // Swap the pivot with the element at the index of smaller elements
        int temp = nums[i + 1];
        nums[i + 1] = nums[high];
        nums[high] = temp;
        // Return the partition point
        return i + 1;
    }
}

Output:

1 2 3 4 5 6 7 8 9

Explanation:

1. Initialization:

• The main method initializes an array of integers named nums.

2. QuickSort Method:

• The quickSort method is the main entry point for the QuickSort algorithm. It takes an array, the low index, and the high index as parameters.

3. Partition Method:

• The partition method selects a pivot element (in this case, the rightmost element) and rearranges the array such that elements smaller than the pivot are on the left, and elements greater than the pivot are on the right. It returns the index of the pivot element after rearrangement.

4. Recursion:

• The quickSort method is then called recursively on the left and right sub-arrays.

5. Base Case:

• The base case for the recursion is when a sub-array has zero or one element, in which case it is already considered sorted.

6. Combine:

• As the recursion unfolds, the sorted sub-arrays are combined to produce the final sorted array.

Time Complexity of QuickSort:

The time complexity of the QuickSort algorithm is O(n log n) on average. However, in the worst-case scenario, it can degrade to O(n²). The average-case time complexity makes QuickSort one of the fastest sorting algorithms for large datasets.

• Average Case (O(n log n)): On average, QuickSort efficiently divides the array into subproblems, and the partitioning process eliminates a constant fraction of elements, leading to a balanced recursion tree. The average-case time complexity is therefore O(n log n).
• Worst Case (O(n²)): The worst-case scenario occurs when the pivot selection consistently results in highly unbalanced partitions. This leads to a skewed recursion tree, and the time complexity becomes O(n²). However, with proper pivot selection strategies, the worst case is rarely encountered in practice.

Space Complexity of QuickSort:

The space complexity of QuickSort is O(log n) due to its recursive nature. Each recursive call adds a new frame to the call stack, and the maximum depth of the call stack corresponds to the logarithm of the input size.

• Best Case Space Complexity (O(log n)): In the best case, when the recursion tree is balanced, the space complexity is O(log n).
• Worst Case Space Complexity (O(n)): In the worst case, when the recursion tree is skewed, the space complexity approaches O(n) due to the maximum depth of the call stack.

QuickSort is often considered an “in-place” sorting algorithm because it doesn’t require additional memory proportional to the size of the input array. However, the recursive nature of the algorithm contributes to the call stack, affecting the space complexity.