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.
