Knowra Quicksort Quicksort Quicksort is a comparison-based sorting algorithm that partitions elements around a pivot, then recursively sorts the resulting subarrays. Its average running time is O(n log n), though poor pivot choices can make it O(n²).
Partition scheme : A procedure that rearranges an array around a pivot so elements fall into specified groups. Partitioning is the operation that creates quicksort’s recursive subarrays.
Merge sort : A comparison sort that recursively divides data, sorts each half, and merges the sorted halves. Unlike typical quicksort, it guarantees O(n log n) time but needs auxiliary storage for arrays.
Comparison sort : A sorting algorithm that determines order by comparing pairs of elements. Quicksort belongs to this family, whose general worst-case lower bound is Ω(n log n).
Quicksort in the C standard library : The sorting routine exposed as qsort by the C standard library, with implementation details left to the library. The name reflects quicksort, but implementations may use different algorithms and guarantees.
Lomuto partition scheme : A partitioning procedure that moves elements no greater than a pivot before it, then places the pivot in its final position. Its simple single-boundary scan makes quicksort’s partition step easy to implement.
Heapsort : An in-place comparison sort that builds a heap and repeatedly removes its maximum or minimum element. It guarantees O(n log n) worst-case time while quicksort does not.
Divide-and-conquer algorithm : An algorithmic approach that divides a problem into smaller instances, solves them, and combines their results. Quicksort divides by partitioning, then solves the resulting subarrays recursively.
Dual-pivot quicksort : A quicksort variant that partitions elements around two pivots into three regions. It is used by some runtime libraries, including Java’s primitive-array sorting implementation.
Hoare partition scheme : A partitioning procedure that scans inward from both ends and swaps misplaced elements around a pivot. It often performs fewer swaps than Lomuto partitioning, but returns a boundary rather than the pivot’s final index.
Insertion sort : A comparison sort that grows a sorted prefix by inserting each new element into its proper position. Its low overhead makes it effective for the tiny partitions encountered in hybrid quicksort implementations.
Show all 22