Easy to search. Easy to read. Easy to cite with credible sources.

Year: 2009 | Volume: 5 | Issue: 7 | Page No.: 476 - 478

Vandana Sharma, Satwinder Singh and K.S. Kahlon

**Abstract**

** Problem statement: S**everal efficient algorithms were developed to cope with the popular task of sorting. Improved heap sort is a new variant of heap sort. Basic idea of new algorithm is similar to classical Heap sort algorithm but it builds heap in another way. The improved heap sort algorithm requires nlogn-0.788928n comparisons for worst case and nlogn-n comparisons in average case. This algorithm uses only one comparison at each node. Hardware has impact on performance of an algorithm. Since improved heap sort is a new algorithm, its performance on different hardware is required to be measured. **Approach: **In this comparative study the mathematical results of improved heap sort were verified experimentally on different hardware. To have some experimental data to sustain this comparison five representative hardware were chosen and code was executed and execution time was noted to verify and analyze the performance. **Results: **Hardware impact was shown on the performance of improved heap sort algorithm. Performance of algorithm varied for different datasets also. **Conclusion:** The Improved Heap sort algorithm performance was found better as compared to traditional heap sort on different hardware, but on certain hardware it was found best.

log (n!) = nlogn-n loge + θ(log n) ≈ nlogn – 1.442695n

Carlson in^{[6]} proposed a variant of Heap sort needs nlogn + (nlogn) comparisons.

Results of all five Test beds are shown in Table 1. It shows the execution times of improved heap sort algorithm for no. of data items ranging from 5-100 K on all five Test beds. It is observed that as the size of the data increases the performance of the Improved heap sort algorithm improves dramatically as shown in Fig. 1.

In Fig. 1 it is observed that improved heap sort shows better performance on Test bed II. This result was further compared with the results of traditional heap sort on Test bed II as shown in Table 2.

Comparison of performance of traditional heap sort and improved heap sort is
shown in Fig. 2 which clearly shows that improved heap sort
performed better than the traditional heap sort algorithm.

Table 1: | Average sorting time (ms) of improved heap sort algorithm on random data averaged 50 runs |

Table 2: | Average sorting time (ms) of improved heap sort algorithm and traditional Heap sort on Test bed II |

Fig. 1: | Comparison of improved heap sort |

Fig. 2: | Comparison of improved heap sort and traditional heap sort |

**CONCLUSION**

It was verified that improved heap sort showed better performance on all Test beds. On Test bed I and Test bed V improved heap sort took less time for small dataset 5 and 10 K than other Test beds. For higher datasets of 50 and 100 K it took more time on Test bed I and V than on any other Test beds. Performance of improved heap sort was best on Test bed II for all datasets in comparison with other Test beds. However it’s performance on Test bed II was comparable with performance on Test bed IV. Performance of improved heap sort on Test bed III for all datasets was consistent for all datasets. So it is recommended that improved heap sort is most suitable for the hardware configuration mentioned in Test bed II. It takes more time to sort larger datasets on Test bed I and V. In applications where algorithm performance needs to be consistent for all data ranges improved heap sort is suitable for Test bed III. In design and analysis of algorithm effect of caching can be taken in to account. By including memory system performance an algorithm analysis may lead to more correct results. For future work cache performance of improved heap can be studied which may lead more optimization.

" class="btn btn-success" target="_blank">View Fulltext