File QuickSort.h

↰ Parent directory (ADS/sort)

Quicksort (section 12.2): perno() rearranges A[ start .

Definition (ADS/sort/QuickSort.h)

Detailed Description

. end ] around the pivot x = A[ start ], so that the items before its final place j are smaller and the ones after it are not, and the two parts are sorted recursively. With P( n ) = n - 1 comparisons per partition, :math:`[

T( n ) = n - 1 + frac{2}{n} sum_{j=1}^{n-1} T( j ) leq 2 ( n + 1 ) sum_{k=3}^{n+1} frac{1}{k} = O( n log n )

` on average over the permutations, but :math:` n ( n - 1 ) / 2 ` when the pivot is always the smallest item, e.g., on a sorted vector, and also when all the items are equal (exercise 12.4), and then the recursion of quickSort() and of quickSort( L ) is n - 1 calls deep, which the stack of the program must hold. Not stable.

quickSortTuned() combines the improvements of the section: the pivot is the median of A[ start ], A[ ( start + end ) / 2 ] and A[ end ]; the partition of Hoare scans from both ends, swapping the pairs on the wrong sides, so that equal items split evenly and the case of all equal items takes O( n log n ); the parts of at most cutoff items are left to insertionSort(); the recursion is an explicit stack that holds the larger part while the smaller one is sorted, so that it never holds more than :math:` lfloor log_2 n rfloor ` parts. quickSort( L ) sorts a LIST with pointers by moving its items into three lists, smaller, equal and larger than the pivot (exercise 12.1).

The contracts [see File Contract.h]: partition() needs start <= end < n and ends with the pivot in its place, the smaller items before it and the others after it, an audit; quickSort() on a range needs end < n unless the range is empty; the sorts end with the same items sorted, an audit. The functions are defined in QuickSort.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 12.2, https://algoritmicamente.it/materiali/libro/capitoli/cap12.pdf

      1. Hoare, Quicksort, The Computer Journal 5(1), 10-16, 1962, doi:10.1093/comjnl/5.1.10

  1. Sedgewick, Implementing Quicksort programs, Communications of the ACM 21(10), 847-857, 1978, doi:10.1145/359619.359631

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Functions