File Selection.h

↰ Parent directory (ADS/search)

The selection of section 17.1: the item of rank k, the k-th smallest, 1 <= k <= n, the median for k = ceil( n / 2 ), without sorting.

Definition (ADS/search/Selection.h)

Detailed Description

  • selection(), of Hoare: perno() puts its pivot in its place j, the q = j - start + 1 smallest items before it, and the search goes on in the part that holds rank k; with the pivot chosen at random, swapped to A[ start ] before perno(), the expected number of comparisons satisfies :math:` T( n ) leq n + frac{2}{n} sum_{q = lfloor n / 2 rfloor}^{n-1} T( q ) leq c n `, linear for every input;

  • medianOfMedians(), of Blum, Floyd, Pratt, Rivest and Tarjan, linear in the worst case: the pivot is the median of the medians of the groups of 5, which has at least 3 n / 10 items on each side, so that :math:` T( n ) leq T( n / 5 ) + T( 7 n / 10 ) + O( n ) = O( n ) `.

Both rearrange A.

The contracts [see File Contract.h]: 1 <= k <= n, and the item returned has rank k, i.e., fewer than k items are smaller and at least k are not larger, an audit in O( n ). The functions are defined in Selection.tpp.

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

      1. Hoare, Algorithm 65: Find, Communications of the ACM 4(7), 321-322, 1961, doi:10.1145/366622.366647

  1. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, R. E. Tarjan, Time bounds for selection, Journal of Computer and System Sciences 7(4), 448-461, 1973, doi:10.1016/S0022-0000(73)80033-9

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions