File CountingSort.h

↰ Parent directory (ADS/sort)

Counting Sort (section 2.7.5) of integers in [ 0 , k ): B[ v ] counts the occurrences of v, then each v is written B[ v ] times in order; :math:` Theta( n + k ) ` time and :math:` Theta( k ) ` space, linear when k = O( n ).

Definition (`ADS/sort/CountingSort.h`)

Program Listing for File CountingSort.h

Detailed Description

The lower bound :math:` Omega( n log n ) ` of the sorts by comparisons does not apply, since it compares no item: it uses that the keys are small integers. A key out of [ 0 , k ) throws std::out_of_range.

The contracts [see File Contract.h]: each key must be in [ 0 , k ), a precondition checked key by key as the keys are counted; the output sorted and made of the same keys is an audit. The functions are defined in CountingSort.tpp.