Comparative Analysis of Some Pivot Selection Schemes for Quicksort Algorithm

Data sorting is an intriguing problem that has attracted some of the most intense research efforts in the field of computer science for both its theoretical importance and its use in many applications. Quicksort is widely considered to be one of the most efficient sorting techniques, which depends on an appropriate pivot selection technique for its performance. In this study, a sequential quicksort was implemented using six different pivot selection schemes for minimizing the execution time of quicksort algorithm. The schemes were tested together using integer array data type. From the results obtained, median-of-five without random index selection scheme minimizes the execution time of quicksort algorithm by about 23-35% as compared to the other techniques. The results also indicated that there is an overhead associated with random index selection and this can affect the performance of a particular method. Thus, this factor needs to be considered in selecting an optimal pivot selection scheme.