Multi-key quicksort

Multi-key quicksort, also known as three-way radix quicksort,[1] is an algorithm for sorting strings. This hybrid of quicksort and radix sort was originally suggested by P. Shackleton, as reported in one of C.A.R. Hoare's seminal papers on quicksort;[2]: 14  its modern incarnation was developed by Jon Bentley and Robert Sedgewick in the mid-1990s.[3] The algorithm is designed to exploit the property that in many problems, strings tend to have shared prefixes.

One of the algorithm's uses is the construction of suffix arrays, for which it was one of the fastest algorithms as of 2004.[4]

Description

The three-way radix quicksort algorithm sorts an array of N (pointers to) strings in lexicographic order. It is assumed that all strings are of equal length K; if the strings are of varying length, they must be padded with extra elements that are less than any element in the strings.[lower-alpha 1] The pseudocode for the algorithm is then[lower-alpha 2]

algorithm sort(a : array of string, d : integer) is
    if length(a) ≤ 1 or d ≥ K then
        return
    p := pivot(a, d)
    i, j := partition(a, d, p)   (Note a simultaneous assignment of two variables.)
    sort(a[0:i), d)
    sort(a[i:j), d + 1)
    sort(a[j:length(a)), d)

Unlike most string sorting algorithms that look at many bytes in a string to decide if a string is less than, the same as, or equal to some other string; and then turning its focus to some other pair of strings, the multi-key quicksort initially looks at only one byte of every string in the array, byte d, initially the first byte of every string. The recursive call uses a new value of d and passes a subarray where every string in the subarray has exactly the same initial part -- the characters before character d.

The pivot function must return a single character. Bentley and Sedgewick suggest either picking the median of a[0][d], ..., a[length(a)−1][d] or some random character in that range.[3] The partition function is a variant of the one used in ordinary three-way quicksort: it rearranges a so that all of a[0], ..., a[i−1] have an element at position d that is less than p, a[i], ..., a[j−1] have p at position d, and strings from j onward have a d'th element larger than p. (The original partitioning function suggested by Bentley and Sedgewick may be slow in the case of repeated elements; a Dutch national flag partitioning can be used to alleviate this.[5])

Practical implementations of multi-key quicksort can benefit from the same optimizations typically applied to quicksort: median-of-three pivoting, switching to insertion sort for small arrays, etc.[6]

See also

Notes
  1. One way to do so without altering the in-memory representation of the strings is to index them using a function that returns −1 or some other small value when the index is out of range.
  2. Arrays and strings are zero-indexed. An array slice a[i:j) yields the subarray of a from i to j (exclusive) and is assumed to be a non-copying, constant-time operation.

References
  1. Public Domain This article incorporates public domain material from Paul E. Black. "multikey Quicksort". Dictionary of Algorithms and Data Structures. NIST.
  2. Hoare, C. A. R. (1962). "Quicksort". Comput. J. 5 (1): 10–16. doi:10.1093/comjnl/5.1.10.
  3. Bentley, Jon; Sedgewick, Robert (1997). Fast algorithms for sorting and searching strings (PDF). Proc. Annual ACM-SIAM Symp. on Discrete Algorithms (SODA). ISBN 0-89871-390-0.
  4. Manzini, Giovanni; Ferragina, Paolo (2004). "Engineering a Lightweight Suffix Array Construction Algorithm". Algorithmica. 40: 33–50. CiteSeerX 10.1.1.385.5959. doi:10.1007/s00453-004-1094-1.
  5. Kim, Eunsang; Park, Kunsoo (2009). "Improving multikey Quicksort for sorting strings with many equal elements". Information Processing Letters. 109 (9): 454–459. doi:10.1016/j.ipl.2009.01.007.
  6. Bentley, Jon; Sedgewick, Robert (1998). "Sorting Strings with Three-Way Radix Quicksort". Dr. Dobb's Journal.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.