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 Summary

    Constructors
    Constructor
    Description
    Quicksort()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    sort(int[] elements)
    Sorts the elements in-place silently.
    void
    sort(int[] elements, boolean trace)
    Sorts the elements in-place, optionally emitting step-by-step traces to visualize the algorithmic progression.

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • Quicksort

      public Quicksort()

  • Method Details

    • sort

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

    • sort

      public void sort(int[] elements, boolean trace)
      Description copied from interface: SortingAlgorithm
      Sorts the elements in-place, optionally emitting step-by-step traces to visualize the algorithmic progression.
      Specified by:
      sort in interface SortingAlgorithm
      Parameters:
      elements - The array of integers to be sorted.
      trace - If true, logs the internal state during execution.