Home   >   CSC-OpenAccess Library   >    Manuscript Information
Full Text Available

(335.78KB)
This is an Open Access publication published under CSC-OpenAccess Policy.
Publications from CSC-OpenAccess Library are being accessed from over 74 countries worldwide.
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 
1 C.A.R. Hoare. "Algorithm 64: Quicksort." Communications of the ACM, vol. 4, pp. 321, Jul. 1961.
2 R. Loeser. "Some performance tests of: quicksort: and descendants." Communications of the ACM, vol. 17, pp. 143-152, Mar. 1974.
3 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.
4 R. Chaudhuri, A. C. Dempster. "A note on slowing Quicksort," in Proc. SIGCSE , 1993, vol. 25.
5 R. Sedgewick. "Quicksort." PhD dissertation, Stanford University, Stanford, CA, USA, 1975.
6 R. Sedgewick. "The Analysis of Quicksort Programs." Acta Informatica, vol. 7, pp. 327-355, 1977.
7 R. Sedgewick. "Implementing Quicksort programs." Communications of the ACM, vol. 21(10), pp. 847-857, 1978.
8 K. Mehlhorn. "Data Structures and Algorithms," in EATCS Monographs on Theoretical Computer Science, vol. 1. Sortzng and Searchzng, 1984.
9 R.L. Wainwright. "A class of sorting algorithms based on Quicksort." Communications of the ACM, vol. 28(4), pp. 396-402, April 1985.
10 R.L. Wainright. "Quicksort algorithms with an early exit for sorted subfiles." Communications of the ACM, pp. 183-190, 1987.
11 J. Bentley. "Programming Pearl: How to sort." Communications of the ACM, vol. 27(4), 1984.
12 D.R. Musser. Introspective Sorting and Selection Algorithms. Software: Practice and Experience. Wiley, Vol. 27(8), 1997, pp. 983-993.
13 R. Sedgewick. Algorithms in C++. Addison Wesley, 1998.
14 C.A.R. Hoare. "Quicksort." Computer Journal, vol. 5, pp. 10-15, 1962.
15 CORPORATE Tech Correspondence, Technical correspondence. Communications of the ACM, vol. 29(4), pp. 331-335, Apr. 1986.
16 L. Khreisat. "QuickSort: A Historical Perspective and Empirical Study." International Journal of Computer Science and Network Security, vol. 7(12), Dec. 2007.
17 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.
Dr. Laila Khreisat
FDU - United States of America
khreisat@fdu.edu