2011 | OriginalPaper | Buchkapitel
Efficient Non-Quadratic Quick Sort (NQQuickSort)
verfasst von : Amjad M. Daoud, Hussein Abdel-jaber, Jafar Ababneh
Erschienen in: Digital Enterprise and Information Systems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper, we present an engineered sorting algorithm, named NQQuicksort, which is efficient and non quadratic. To avoid the quadratic worst case, and degenerate partitioning performance, NQQuicksort adopts two pivot computations only. The first is the same as the pivot computation in median of three quicksort and the second is similar to that in binary quicksort (radix exchange). The pivot computations applied are quite different and non-related, such that when one pivot computation fails, it gives no indication to whether the second pivot computation step will, or will not succeed (fail). When the first pivot selected results in unbalanced partitioning, the second pivot computation is immediately applied in the next recursive call. NQQuickSort is faster than the tuned quicksort implementation of the Java class library engineered by Bentley and McIlroy [3]. The algorithm and its runtime behavior are discussed in detail. The performance of NQQuicksort is faster than quicksort as well as the fastest variant of radix sorting algorithms; the Least Significant Digit (LSD) radix sort [15].