A Note on the Average Behavior of Heapsort
Using some ideas from Calculus and Stochastic Processes, the sift-up phase and the selection phase of heapsort are analysed with respect to the average number of comparisons and interchanges. In particular a Conservation of Ignorance Theorem is proved: both phases of heapsort preserve the given distribution of the keys to be sorted up to a multiplicative constant for scaling.
Nutzung und Vervielfältigung:
Alle Rechte vorbehalten