login
A350569
a(n)/n! is the average number of key comparisons required to sort n records with distinct keys using a modified heapsort (Algorithm H in Don Knuth's TAOCP Vol. 3, answer to exercise 18).
7
2, 18, 154, 1257, 10152, 91557, 922368, 10286658, 119281680, 1517655690, 20619929376, 303487939485, 4662169420608
OFFSET
2,1
COMMENTS
There are two places in R. W. Floyd's modified algorithm where the keys are compared. The first is in step H4 [Find larger child.] and the second in step H9' [Does K fit?]. The sequence is the sum of the counts of these comparisons, taken over all n! possible orders of the records.
The following table shows the maximum and average number of key comparisons for the original algorithm and for its modified version.
Algorithm H Modified algorithm
.
n Worst case Worst case
| A350426(n) A350427(n)
| | Average | Average
| | 2*A350428(n)/n! | A350569(n)/n!
| | | Average/ | | Average/
| | | (n*log(n)) | | (n*log(n))
2 1 1.000 0.721 1 1.000 0.721
3 3 3.000 0.910 3 3.000 0.910
4 7 6.500 1.172 7 6.417 1.157
5 12 10.950 1.361 12 10.475 1.302
6 17 15.133 1.408 16 14.100 1.312
7 22 19.789 1.453 20 18.166 1.334
8 29 25.814 1.552 27 22.876 1.375
9 37 32.524 1.645 34 28.347 1.433
10 44 38.631 1.678 39 32.871 1.428
11 51 45.237 1.715 44 38.020 1.441
12 59 51.845 1.739 51 43.048 1.444
13 66 59.021 1.770 57 48.737 1.462
14 73 65.488 1.773 63 53.479 1.447
This is compatible with Don Knuth's remark, quoted from TAOCP Vol. 3, page 148: Heapsort has the interesting property that its worst case isn't much worse than the average.
REFERENCES
D. E. Knuth, The Art of Computer Programming Second Edition. Vol. 3, Sorting and Searching. Chapter 5.2.3 Sorting by Selection, Pages 145, 156 and 642. Addison-Wesley, Reading, MA, 1998.
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Hugo Pfoertner, Jan 06 2022
STATUS
approved