2011 | OriginalPaper | Chapter
Efficient Non-Quadratic Quick Sort (NQQuickSort)
Authors : Amjad M. Daoud, Hussein Abdel-jaber, Jafar Ababneh
Published in: Digital Enterprise and Information Systems
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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].