Home   >   CSC-OpenAccess Library   >    Manuscript Information
A Survey of Adaptive QuickSort Algorithms
Laila Khreisat
Pages - 1 - 10     |    Revised - 31-01-2018     |    Published - 30-04-2018
Volume - 12   Issue - 1    |    Publication Date - April 2018  Table of Contents
MORE INFORMATION
KEYWORDS
Algorithm, Survey, Quicksort, Sorting, Adaptive Sorting.
ABSTRACT
In this paper, a survey of adaptive quicksort algorithms is presented. Adaptive quicksort algorithms improve on the worst case behavior of quicksort when the list of elements is sorted or nearly sorted. These algorithms take into consideration the already existing order in the input list to be sorted. A detailed description of each algorithm is provided. The paper provides an empirical study of these algorithms by comparing each algorithm in terms of the number of comparisons performed and the running times when used for sorting arrays of integers that are already sorted, sorted in reverse order, and generated randomly.
1 Google Scholar 
2 BibSonomy 
3 Doc Player 
4 Scribd 
5 SlideShare 
C.A.R. Hoare. "Algorithm 64: Quicksort." Communications of the ACM, vol. 4, pp. 321, Jul. 1961.
C.A.R. Hoare. "Quicksort." Computer Journal, vol. 5, pp. 10-15, 1962.
CORPORATE Tech Correspondence, Technical correspondence. Communications of the ACM, vol. 29(4), pp. 331-335, Apr. 1986.
D.R. Musser. Introspective Sorting and Selection Algorithms. Software: Practice and Experience. Wiley, Vol. 27(8), 1997, pp. 983-993.
J. Bentley. "Programming Pearl: How to sort." Communications of the ACM, vol. 27(4), 1984.
J.L. Bentley, R. Sedgewick, R. "Fast algorithms for sorting and searching strings," in Proc. 8th Annual ACM-SIAM symposium on Discrete algorithms, 1997, pp. 360-369.
K. Mehlhorn. "Data Structures and Algorithms," in EATCS Monographs on Theoretical Computer Science, vol. 1. Sortzng and Searchzng, 1984.
L. Khreisat. "QuickSort: A Historical Perspective and Empirical Study." International Journal of Computer Science and Network Security, vol. 7(12), Dec. 2007.
M. Matsumoto, T. Nishimura. "Mersenne Twister: A 623-dimensionally equidistributed uniform pseudorandom number generator." ACM Trans. on Modeling and Computer Simulation, vol. 8(1), pp.3-30, Jan. 1998.
R. Chaudhuri, A. C. Dempster. "A note on slowing Quicksort," in Proc. SIGCSE , 1993, vol. 25.
R. Loeser. "Some performance tests of: quicksort: and descendants." Communications of the ACM, vol. 17, pp. 143-152, Mar. 1974.
R. Sedgewick. "Implementing Quicksort programs." Communications of the ACM, vol. 21(10), pp. 847-857, 1978.
R. Sedgewick. "Quicksort." PhD dissertation, Stanford University, Stanford, CA, USA, 1975.
R. Sedgewick. "The Analysis of Quicksort Programs." Acta Informatica, vol. 7, pp. 327-355, 1977.
R. Sedgewick. Algorithms in C++. Addison Wesley, 1998.
R.L. Wainright. "Quicksort algorithms with an early exit for sorted subfiles." Communications of the ACM, pp. 183-190, 1987.
R.L. Wainwright. "A class of sorting algorithms based on Quicksort." Communications of the ACM, vol. 28(4), pp. 396-402, April 1985.
Dr. Laila Khreisat
FDU - United States of America
khreisat@fdu.edu


CREATE AUTHOR ACCOUNT
 
LAUNCH YOUR SPECIAL ISSUE
View all special issues >>
 
PUBLICATION VIDEOS