Multikey Quicksort for Sorting String Using Predecessor and Successor Pivots

Abstract

Quicksort is one of the most popular internal sorting algorithms. In this research, we propose multikey quicksort for sorting sequence of integers and strings using predecessor pivots, successor pivots and the collect-center partition. Predecessor pivots and successor pivots are used to reduce the recursive calls while the collect-center partitioning is used to reduce the number of swaps. We compare the performance of our algorithm, called CC5sort, with the performance of the quicksort using adjacent pivot quicksort and the original collect-center partition. We tested an efficiency of CC5sort in four different types of data sets; nearly sorted data, nearly reverse sorted data, repeated element data and random ordered data. Our experiments show that CC5sort significantly exhibits the faster running time for random ordered data with a lot of repeated elements than collect-center partitioning and APQsort.