Quicksort Algorithm—An Empirical Study

Quick sort is one of the most sought after algorithms, because if implemented properly quick sort could be much faster than its counterparts, merge sort and heapsort. The main crux of quick sort algorithm is the implementation of the partitioning operation. Nico Lomuto and C. A. R Hoare have put forth partitioning algorithms that have gained prominent significance. Despite this, one can always shed more light on this partially understood operation of partition. Sorting algorithms have been further developed to enhance its performance in terms of computational complexity, memory and other factors. The proposed method is the use of randomized pivot in the implementation of Lomuto partition and Hoare partition algorithms, respectively. It is analysed with and without a randomized pivot element. This paper presents a comparison of the performance of a quick sort algorithm in different cases using contrasting partition approaches with and without randomized pivot. The results provide a theoretical explanation for the observed behaviour and give new insights on behaviour of quick sort algorithm for different cases. The Hoare partition approach with randomized pivot gives best time complexity in comparison to the other cases.