The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A350428 2*a(n)/n! is the average number of key comparisons required to sort n records with distinct keys using heapsort (Algorithm H in Don Knuth's TAOCP Vol. 3) 4
 1, 9, 78, 657, 5448, 49869, 520416, 5901138, 70092000, 902850273, 12416814432, 183763314090, 2854581512832 (list; graph; refs; listen; history; text; internal format)
 OFFSET 2,2 COMMENTS There are two places in the algorithm where the keys are compared. The first is in step H4 [Find larger child.] and the second in step H6 [Larger than K?]. The sequence is the sum, divided by 2, of the counts of these comparisons, taken over all n! possible orders of the records. REFERENCES D. E. Knuth, The Art of Computer Programming Second Edition. Vol. 3, Sorting and Searching. Chapter 5.2.3 Sorting by Selection, Page 145. Addison-Wesley, Reading, MA, 1998. LINKS Table of n, a(n) for n=2..14. CROSSREFS Cf. A350426, A350427. A350569 contains a table with the maximum and average number of comparisons for the original algorithm and for its modified version. Sequence in context: A000445 A046196 A231596 * A190980 A254657 A231590 Adjacent sequences: A350425 A350426 A350427 * A350429 A350430 A350431 KEYWORD nonn,more AUTHOR Hugo Pfoertner, Jan 05 2022 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified April 18 16:22 EDT 2024. Contains 371780 sequences. (Running on oeis4.)