Performance analysis of a new varient of heasport

Abstract

Sorting is a classical problem in Computer Science. Sorting quently used algorithm in computer and many other subjects where it is related directly or indirectly. Thus any improvement of sorting algorithm will be of great value. Heapsort is one of the good internal sorting algorithms. It has moderate performance both in average case and worst case. This work is an attempt to Improve the heapsort algorithm and perform a comparative performance analysis. In this work a set of heapsort variants have been thoroughly studied theoretically and their relative performance have been evaluated by carefully designed experiments. The sorting time directly depends on two factorselement- comparison and element-movement. These two factors are taken into account for comparing different heapsort variants. From Paulik's generalized heapsort, it is proved that heapsort on 3-heap is the best in top-down case. A method is developed for obtaining a worst heap in top-down sorting and this worst heap is used throughout the work for analyzing heapsort in worst case. New heapsort variants, in top-down and bottom-up on 3-heap, are. proposed having improved performance. Relative performance studies are made between these new variants and existing good heapsort variants. Since quicksort is the best ever known internal sorting algorithm and mergesort is one of the best both in external and internal sorting algorithm, an experiment is made on basis of time complexity in average case for these two and new heapsort variants. This study have placed the heapsort algorithm in a strong position against quicksort and mergesort.