A Note on the Average Behavior of Heapsort

Doberkat, Ernst-Erich GND

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.

Vorschau

Zitieren

Zitierform:

Doberkat, Ernst-Erich: A Note on the Average Behavior of Heapsort. Hagen 1980. FernUniversität in Hagen.

Zugriffsstatistik

Gesamt

Volltextzugriffe:
Metadatenansicht:

12 Monate

Volltextzugriffe:
Metadatenansicht:

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export

powered by MyCoRe