Sorting
Beside the sorts of the book, ADS has the classical ones that the book
leaves out and the engineered ones of the current libraries. They are
tested in test/sorting.cpp on all the permutations of
up to 7 items and on the patterns that usually defeat a sort (sorted,
reversed, sawtooth, organ pipe, few distinct keys), and measured by
bench/sort.cpp against std::sort, std::stable_sort
and Boost.Sort (make bench, or CMake with -DADS_BENCHMARKS=ON).
ADS::sort() and ADS::stableSort()
(sort/Sort.h) choose among them by the type of
the items and by the order, i.e., the radix sort for numbers, the MSD
radix sort for strings, and pdqsort and Powersort for the rest, with
thresholds chosen on the measures of results/.
What |
Header |
|---|---|
bubble, cocktail shaker, odd-even transposition, comb and gnome sort |
|
cycle sort (fewest writes) and pancake sort (prefix reversals) |
|
tree sort, patience sort, smoothsort, strand sort |
|
sorting networks of Batcher (merge exchange, bitonic) |
|
stooge sort, slow sort, bogo sort |
|
introsort, pdqsort, dual-pivot and three-way quicksort |
|
Timsort and Powersort |
|
LSD radix sort of numbers and by a key, American flag sort, MSD radix sort of strings, bucket sort |
|
multikey quicksort of strings |
|
sort of strings by integer keys of 8 characters, sorted in the vector registers |