A NEW PIVOT SELECTION SCHEME FOR QUICKSORT ALGORITHM
Keywords:
Data sorting, partitioning, pivot selection scheme, sequential quicksort algorithmAbstract
Data sorting is one of the most intensively studied problems in computing science for both its theoretical importance and its use in many applications. Quicksort which depends on an appropriate pivot selection technique for its performance is widely considered to be one of the most efficient sorting techniques. Brest et al. (2000) has implemented a parallel quicksort algorithm on PC-cluster using a Median5 function as a pivot selection scheme. In this paper, a sequential quicksort was implemented using Median5 function as a pivot selection scheme and subsequently a new pivot selection scheme for minimizing the execution time of quicksort algorithm sequentially is proposed. The two schemes were tested together using integer and double array data types. From the results obtained, the execution time of quicksort algorithm was reduced by about 23-28% for integer array and 17-22% for double array when compared with Median5 function (median-of-five with random index selection scheme).
References
Brest, J., Vreze, A., and Zumer, V. (2000). A Sorting algorithm on PC cluster. Proceedings of the ACM Symposium on Applied Computing; March 19-21, 2000; Como, Italy. ACM Press, New York, NY, USA, p. 710-715.
Cerin, C. (2002). An out-of-core sorting algorithm clusters with processors at different speed. IEEE Proceedings of the Int. Parallel and Distributed Processing Symposium; April 15-19, 2002; Fort Lauderdale, Florida, USA. IEEE Computer Society, Washington, DC, USA, p. 681-686.
Hoare, C.A.R. (1961). Algorithm 64; Quicksort. Comm. ACM. 4(7):321.
Hoare, C.A.R. (1962). Quicksort. Computer Journal, 5:10-15.
Knuth, D.E. (1998). The Art of Computer Programming. 2nd ed. Addison Wesley, Boston, USA, 3:73-80.
Loeser, R. (1974). Some performance test of quicksort and descendents. Commun. ACM., 17(3):143-152.
Moh, S., Kim, S., Lee, M., Yu, C., and Han, D. (1999). A new parallel quicksort with efficient processor allocation and minimal communication. SIG on Parallel Processing System Conference; September 10-11, 1999; Korea Information Science Society, Seoul, Korea, p. 83-90.
Motzkin, D. (1983). Meansort. Comm. ACM., 26(4):250-251.
Roger, L.W. (1985). A class of sorting algorithms based on quicksort. Commun. ACM., 28(4):396-402.
Scowen, R.S. (1965). Algorithm 271; Quickersort. Comm. ACM. 8, 11:669-670.
Sedgewick, R. (1975). Quicksort. [PhD. thesis]. Stanford Comptr. Sci. Rep. STAN-CS-75- 492, Stanford U., Stanford, California, p. 25-251.
Sedgewick, R. (1977). Quicksort with equal keys. Siam Journal on Comput., 6(2): 240-267.
Sedgewick, R. (1978). Implementing quicksort program. Commun. ACM., 21(10):847-857.
Singleton, R.C. (1969). Algorithm 347; An efficient algorithm for sorting with minimal storage. Comm. ACM., 12(3):185-187.
van Emden, M.H. (1970). Increasing the efficiency of quicksort. Comm. ACM., 13(9):563-567.
Weiss, M.A. (1999). Data Structure and Algorithm Analysis in C++. 2nd ed. Addisson-Wesley Publishing Inc, Boston, USA, p. 250-467.
Youran, L., and Magdi, A.M. (1992). Parallel quicksort in hypercube. ACM/SIGAPP Symposium on Applied Computing; March 1-3, 1992; Kansas City, Missouri, United States. ACM Press, New York, NY, USA, p. 740-746.
Zumer, V., Ojstersek, M., Vreze, A., and Brest, J. (1999). Sorting on heterogeneous computing System. Proceeding of MIPRO’99: 10th International Conference on Computers in Intelligent Systems; May 17-21, 1999; Opatia, Croatia, p. 1-4.
