Quick Sort in Java

What is Quick Sort?

QuickSort is a highly efficient, divide-and-conquer sorting algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted.

How Quick Sort Works

1. Choose a Pivot: Select an element from the array to be the pivot.
2. Partition: Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it. After this partitioning, the pivot is in its final position.
3. Recursion: Recursively apply the above steps to the sub-array of elements with smaller values and the sub-array of elements with greater values.

Implementation of Quick Sort in Java

Here's a Java implementation of the Quick Sort algorithm:

 public class QuickSort {

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int partitionIndex = partition(arr, low, high);

            quickSort(arr, low, partitionIndex - 1);  // Sort left sub-array
            quickSort(arr, partitionIndex + 1, high); // Sort right sub-array
        }
    }

    private static int partition(int[] arr, int low, int high) {
        // Choosing the rightmost element as pivot
        int pivot = arr[high];
        int i = (low - 1); // Index of smaller element
        for (int j = low; j < high; j++) {
            // If current element is smaller than or equal to 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 arr[high] (or pivot)
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        int n = arr.length;
        quickSort(arr, 0, n - 1);

        System.out.println("Sorted array:");
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
} 

Explanation of the Code:

• The quickSort method takes the array, the low index, and the high index as input.
• The partition method chooses a pivot (in this case, the last element) and partitions the array around it.
• The main method demonstrates how to use the quickSort method.

Pivot Selection Strategy

The choice of the pivot significantly impacts the performance of Quick Sort. Here are a few common pivot selection strategies:

• First Element: Simply choose the first element of the array as the pivot. This is easy to implement but can lead to poor performance, especially if the array is already sorted or nearly sorted.
• Last Element: Choose the last element of the array as the pivot. Similar to the first element, this can lead to O(n^2) performance in sorted or nearly sorted arrays. The example code above uses this strategy for simplicity.
• Random Element: Choose a random element from the array as the pivot. This helps to avoid worst-case scenarios by making the choice independent of the input data.
• Median-of-Three: Choose the median of the first, middle, and last elements of the array as the pivot. This can provide a better pivot than simply choosing the first, last, or a random element, especially for partially sorted arrays.

The Random Element and Median-of-Three strategies are generally preferred as they reduce the likelihood of encountering worst-case scenarios.

Time and Space Complexity

Time Complexity:

• Best Case: O(n log n) - Occurs when the pivot is always the middle element (or close to it). This leads to balanced partitions.
• Average Case: O(n log n) - Occurs when the pivot selection consistently results in reasonably balanced partitions.
• Worst Case: O(n²) - Occurs when the pivot is consistently the smallest or largest element, leading to highly unbalanced partitions. This often happens when sorting an already sorted or nearly sorted array using the first or last element as the pivot.

Space Complexity:

• Best Case: O(log n) - Due to the recursive calls. The depth of the recursion is logarithmic.
• Average Case: O(log n) - Similar to the best case.
• Worst Case: O(n) - Occurs when the recursion depth becomes linear due to unbalanced partitions.

Note: The space complexity can be reduced to O(1) (in-place sorting) with an iterative implementation of Quick Sort, although the recursive implementation is more common.

Quick Sort in Competitive Programming (Java) with Solutions

Quick Sort is frequently used in competitive programming due to its generally good performance. Here are examples with explanations:

Example 1: Sorting an Array of Integers

Problem: Given an array of integers, sort it in ascending order using Quick Sort.

Solution:

 import java.util.Arrays;
import java.util.Random;

class Solution {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int partitionIndex = partition(arr, low, high);

            quickSort(arr, low, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        // Implementing Random Pivot Selection for better average case performance.
        Random random = new Random();
        int randomIndex = low + random.nextInt(high - low + 1); // Get a random index between low and high, inclusive.
        swap(arr, randomIndex, high); // Swap the random element with the last element (our chosen pivot location).

        int pivot = arr[high]; // Pivot is at the 'high' position.
        int i = (low - 1);

        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 1, 5, 6};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr)); // Output: [1, 2, 5, 5, 6, 9]
    }
} 

Explanation: This code implements Quick Sort with a random pivot selection strategy to avoid worst-case scenarios. The partition method now selects a random element as the pivot before proceeding with the usual partitioning process.

Example 2: Sorting an Array of Strings (Lexicographically)

Problem: Given an array of strings, sort it lexicographically (alphabetical order) using Quick Sort.

Solution:

 import java.util.Arrays;
import java.util.Random;

class Solution {
    public static void quickSort(String[] arr, int low, int high) {
        if (low < high) {
            int partitionIndex = partition(arr, low, high);

            quickSort(arr, low, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, high);
        }
    }

    private static int partition(String[] arr, int low, int high) {
        Random random = new Random();
        int randomIndex = low + random.nextInt(high - low + 1);
        swap(arr, randomIndex, high);

        String pivot = arr[high];
        int i = (low - 1);

        for (int j = low; j < high; j++) {
            if (arr[j].compareTo(pivot) <= 0) { // Using compareTo for string comparison
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }

    private static void swap(String[] arr, int i, int j) {
        String temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        String[] arr = {"banana", "apple", "cherry", "date"};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr)); // Output: [apple, banana, cherry, date]
    }
} 

Explanation: This is very similar to the integer sorting, but instead of using <= for comparison, it uses the compareTo method of the String class. compareTo returns a negative value if the first string is lexicographically less than the second, 0 if they are equal, and a positive value if the first string is lexicographically greater than the second.

Example 3: K-th Smallest Element using Quick Sort

Problem: Find the k-th smallest element in an unsorted array. (This leverages the partitioning aspect of Quick Sort for efficiency.)

Solution:

 import java.util.Random;

class Solution {
    public static int findKthSmallest(int[] arr, int k) {
        return findKthSmallestHelper(arr, 0, arr.length - 1, k);
    }

    private static int findKthSmallestHelper(int[] arr, int low, int high, int k) {
        if (k > 0 && k <= high - low + 1) {
            int partitionIndex = partition(arr, low, high);

            if (partitionIndex - low == k - 1)
                return arr[partitionIndex];

            if (partitionIndex - low > k - 1)
                return findKthSmallestHelper(arr, low, partitionIndex - 1, k);

            return findKthSmallestHelper(arr, partitionIndex + 1, high, k - partitionIndex + low - 1);
        }
        return Integer.MAX_VALUE;  // Indicate invalid input.
    }

    private static int partition(int[] arr, int low, int high) {
        Random random = new Random();
        int randomIndex = low + random.nextInt(high - low + 1);
        swap(arr, randomIndex, high);

        int pivot = arr[high];
        int i = (low - 1);

        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {7, 10, 4, 3, 20, 15};
        int k = 3;
        System.out.println("K'th smallest element is " + findKthSmallest(arr, k)); // Output: K'th smallest element is 7
    }
} 

Explanation: This solution uses the partition function from Quick Sort to find the k-th smallest element *without* fully sorting the array. After partitioning, if the pivot is at the (k-1)-th position relative to the subarray, then the pivot is the k-th smallest element. If not, we recursively search in the appropriate sub-array. This approach has an average time complexity of O(n), which is significantly better than sorting the entire array.

Important Notes for Competitive Programming:

• Pivot Selection: Always consider using a randomized pivot selection or median-of-three to avoid worst-case time complexity, especially when dealing with potentially pre-sorted data.
• Space Complexity: Be mindful of space constraints. In some situations, you might need to consider an iterative (in-place) implementation of Quick Sort to reduce space usage.
• Built-in Sorting: Java's Arrays.sort() is highly optimized (often using a variant of Quick Sort or Merge Sort) and may be faster than a hand-rolled Quick Sort implementation, especially for smaller arrays. Use it when possible unless you need the specific partitioning behavior for problems like finding the k-th smallest element.
• Stack Overflow: For very large arrays, the recursive calls in Quick Sort can lead to a stack overflow. In such cases, use an iterative version of the algorithm or consider using Merge Sort, which has a guaranteed O(n log n) time complexity and a smaller stack depth (or no stack depth if implemented iteratively).