Abstrakt

Engineering of a Quicksort Partitioning Algorithm

D.Abhyankar and M.Ingle

One of the most sophisticated sorting algorithm in sorting literature is Quicksort. Though Quicksort has several striking aspects, design of partition function is the central aspect of the Quicksort algorithm. Partitioning is a meticulously researched area in which we find Hoare Partition and Lomuto Partition as two prominent partition algorithms in the literature. Despite the fact that much effort has been targeted on research into partitioning, it seems that partitioning is still inadequately understood and amenable to a right blend of optimizations. Superior partitioning algorithms can be designed using a perfect blend of performance improving measures and a touch of elegance. This paper postulates two novel partition algorithms which are better than the existing ones. Proposed algorithm3 apply some effective optimizations and because of this instruction count gets reduced. Reduced instruction count helps the function in gaining spectacular performance. Presented algorithm4 is an elegant algorithm which is compact and intenselycompetitive from performance point of view.