Quick Sort

Quick Sort

Quick sort also follows the divide and conquer paradigm (Similar to Merge Sort)

How it works

1. It works by partitioning an array into two subarrays, then sorting the subarrays independently.
2. Quicksort is complementary to mergesort:
   1. For mergesort
      1. We break the array into two subarrays to be sorted and then combine the ordered subarrays to make the whole ordered array;
      2. We do the two recursive calls before working on the whole array;
      3. The array is divided in half;
   2. For quicksort
      1. we rearrange the array such that, when the two subarrays are sorted, the whole array is ordered.
      2. We do the two recursive calls after working on the whole array.
      3. The position of the partition depends on the contents of the array.

Pros

1. The quicksort algorithm’s desirable features are
   1. it is in-place (uses only a small auxiliary stack)
   2. it requires time proportional to N log N on the average to sort an array of length N.
2. None of the other algorithms consider combining these two properties.
3. Furthermore, quicksort has a shorter inner loop than most other sorting algorithms, which means that it is fast in practice as well as in theory.

https://github.com/explorer436/programming-playground/tree/main/java-playground/my-java-solutions/src/main/java/com/my/company/sorting

https://github.com/explorer436/programming-playground/blob/main/haskell-playground/haskell-solutions/src/sorting/algorithms/Quicksort.org

https://github.com/explorer436/programming-playground/blob/main/java-playground/my-java-solutions/src/main/java/com/my/company/sorting/algorithms/Quicksort.java

TODO

1. https://www.geeksforgeeks.org/lomuto-partition-algorithm/
2. https://www.geeksforgeeks.org/hoares-vs-lomuto-partition-scheme-quicksort/

Explanation

How Quicksort Works using Lomuto partition scheme

With this partition scheme, the pivot is typically chosen as the last element of the sub-array.

1. Divide:

   1. Choose a Pivot: Select an element from the array. This element is called the “pivot”. The choice of pivot is crucial for performance. Common strategies include:
      1. Picking the first element.
      2. Picking the last element (Lomuto partition).
      3. Picking a random element.
      4. Picking the median-of-three (median of the first, middle, and last elements). This is often a good compromise.
   2. Partition:
      1. Rearrange the array (or sub-array) so that all elements smaller than the pivot come before it, and all elements greater than the pivot come after it. Elements equal to the pivot can go on either side. After partitioning, the pivot is in its final sorted position. The `partition()` method returns the index of this pivot.

2. Conquer:

   1. Recursively apply Quicksort to the sub-array of elements to the left of the pivot (elements smaller than the pivot).
   2. Recursively apply Quicksort to the sub-array of elements to the right of the pivot (elements larger than the pivot).

3. Combine:

   1. This step is trivial in Quicksort because the sorting is done “in-place” within the recursive calls. Once the sub-arrays are sorted, the entire array is sorted.

Base Case for Recursion

The recursion stops when a sub-array has zero or one element, as such arrays are already considered sorted. This is handled by the `if (low < high)` condition.

Characteristics of Quicksort

1. Time Complexity:
   1. Best Case: O(n log n) - Occurs when the pivot selection consistently divides the array into roughly equal halves.
   2. Average Case: O(n log n) - Generally performs very well in practice.
   3. Worst Case: O(n²) - Occurs when the pivot selection is consistently poor (e.g., always picking the smallest or largest element in an already sorted or reverse-sorted array). This leads to highly unbalanced partitions, essentially degenerating into something like selection sort.
2. Space Complexity:
   1. Average Case: O(log n) - Due to the recursion call stack depth.
   2. Worst Case: O(n) - If the recursion tree is skewed (similar to the worst-case time complexity scenario), the call stack can grow to the size of the array.
3. In-place: Yes, Quicksort modifies the array directly and typically requires only a small, constant amount of extra space for variables (plus the recursion stack).
4. Stability: Not stable by default. The relative order of equal elements might change after sorting. For example, if you have two ‘5’s, their original order isn’t guaranteed to be preserved.
5. Comparison Sort: It’s a comparison sort, meaning it sorts by comparing elements.

Improvements and Considerations

1. Pivot Selection:
   1. Random Pivot: Choosing a random pivot helps avoid the worst-case O(n²) behavior on already sorted or specific input patterns.
   2. Median-of-Three: Calculate the median of the first, middle, and last elements of the sub-array and use that as the pivot. This further reduces the chance of worst-case scenarios.
2. Handling Small Sub-arrays:
   1. For very small sub-arrays (e.g., fewer than 10-20 elements), the overhead of recursion can make Quicksort less efficient than simpler algorithms like Insertion Sort. A common optimization is to switch to Insertion Sort when `high - low + 1` is below a certain threshold.
3. Duplicate Keys (3-Way Partitioning):
   1. If the array contains many duplicate keys, the standard 2-way partitioning (like Lomuto or Hoare) can be inefficient.
   2. 3-Way Partitioning (Dutch National Flag problem): This scheme partitions the array into three parts: elements less than the pivot, elements equal to the pivot, and elements greater than the pivot. Then, it only recursively sorts the “less than” and “greater than” parts. This is highly effective for arrays with many duplicates.
4. Tail Call Optimization (or Iterative Approach):
   1. Java doesn’t have true tail-call optimization. To avoid potential stack overflow on very large arrays (especially in worst-case scenarios), one can implement Quicksort iteratively using an explicit stack, or optimize one of the recursive calls into a loop (usually the one for the larger partition to keep stack depth O(log n)).

This implementation provides a solid foundation for understanding and using Quicksort in Java.