File MultikeyQuickSort.h

↰ Parent directory (ADS/sort)

The multikey quicksort of Bentley and Sedgewick, beyond the book: the quicksort of strings by one character at a time, a partition into three parts, the strings whose character d is smaller, equal and larger than that of the pivot, the equal part going on with the character d + 1 and the others with d.

Definition (ADS/sort/MultikeyQuickSort.h)

Detailed Description

It is the sort that corresponds to the ternary search tree of the same paper, and makes :math:` O( D + n log n ) ` comparisons of characters for D the total length of the distinguishing prefixes, against the :math:` O( n log n ) ` comparisons of whole strings of a quicksort, each as long as their common prefix. It sorts in place, not stable.

The contracts [see File Contract.h]: the vector ends with the same strings sorted, an audit. The function is defined in MultikeyQuickSort.tpp.

    1. Bentley, R. Sedgewick, Fast algorithms for sorting and searching strings, Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms (SODA), 360-369, 1997

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions