Class Quicksort

java.lang.Object
topics.sorting.quicksort.Quicksort
All Implemented Interfaces:
SortingAlgorithm
public class Quicksort extends Object implements SortingAlgorithm

Quicksort (Median-of-Three)

A highly efficient, divide-and-conquer sorting algorithm. This implementation utilizes the "Median-of-Three" heuristic for pivot selection to heavily mitigate the risk of encountering the worst-case performance on already sorted arrays.

Algorithm Steps

  1. Select a pivot using the median value among the left, center, and right elements.
  2. Partition the array so that elements smaller than the pivot are moved to its left, and larger elements to its right.
  3. Recursively apply the same logic to the left and right sub-arrays.
  4. Base case: Sub-arrays of 3 or fewer elements are sorted almost instantly by the median-of-three logic.

Complexity Analysis

  • Time Complexity (Average/Best): O(N log N) - The partition generally halves the array.
  • Time Complexity (Worst): O(N²) - Occurs if the pivot is repeatedly the absolute maximum/minimum (highly unlikely with Median-of-Three).
  • Space Complexity: O(log N) - Stack memory required for the recursive calls.
  • Stability: No - Swapping elements across the pivot boundary disrupts the relative order of equal elements.
Author:
vicegd
See Also:
  • invalid reference 
    topics.sorting.SortingAlgorithm

  • Constructor Details

    • Quicksort

      public Quicksort()

  • Method Details

    • sort

      public void sort(int[] elements)
      Description copied from interface: SortingAlgorithm
      Sorts the elements in-place.
      Specified by:
      sort in interface SortingAlgorithm
      Parameters:
      elements - The array of integers to be sorted.