A350569 -id:A350569 - cp's OEIS frontend

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).

1, 9, 78, 657, 5448, 49869, 520416, 5901138, 70092000, 902850273, 12416814432, 183763314090, 2854581512832

Offset: 2

Hugo Pfoertner, Jan 05 2022

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.

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.

Cf. A350426, A350427.

A350569 contains a table with the maximum and average number of comparisons for the original algorithm and for its modified version.

A350426 a(n) is the maximum number of key comparisons required to sort n records with distinct keys using heapsort (Algorithm H in Don Knuth's TAOCP Vol. 3).

Original entry on oeis.org

1, 3, 7, 12, 17, 22, 29, 37, 44, 51, 59, 66, 73, 80

Offset: 2

Hugo Pfoertner, Jan 05 2022

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 shows the maxima of the counts of these comparisons, determined over all n! possible orders of the records.

a(16) >= 90.

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.

Cf. A350427, A350428.

A350569 contains a table with the maximum and average number of comparisons for the original algorithm and for its modified version.

A350427 a(n) is the maximum 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).

Original entry on oeis.org

1, 3, 7, 12, 16, 20, 27, 34, 39, 44, 51, 57, 63

Offset: 2

Hugo Pfoertner, Jan 05 2022

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 shows the maxima of the counts of these comparisons, determined over all n! possible orders of the records.

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.

Cf. A350426, A350428.

A350569 contains a table with the maximum and average number of comparisons for the original algorithm and for its modified version.

A350567 a(n) is the maximum number of key comparisons required to perform an indirect sort of n records with distinct keys using a two-way merge (A. D. Woodall's mergesort).

Original entry on oeis.org

1, 4, 6, 10, 13, 17, 20, 25, 29, 34, 38, 43, 47, 52

Offset: 2

Hugo Pfoertner, Jan 09 2022

There are six places in the Algol 60 procedure mergesort where the keys are compared. The sequence shows the maxima of the counts of these comparisons, determined over all n! possible orders of the records.

a(16) >= 56.

D. E. Knuth, The Art of Computer Programming Second Edition. Vol. 3, Sorting and Searching. Chapter 5.2.4 Sorting by Merging, Pages 164-166. Addison-Wesley, Reading, MA, 1998.

A. D. Woodall, An internal sorting procedure using a two-way merge, Algorithm 45, The Computer Journal, Volume 13, Number 1, February 1970, Algorithms Supplement, pp. 110-111.

A350568 provides the corresponding average numbers and a comparison table.

Cf. A001768, A001855, A350569.

A350568 a(n)/n! is the average number of key comparisons required to perform an indirect sort of n records with distinct keys using a two-way merge (A. D. Woodall's mergesort).

Original entry on oeis.org

2, 19, 130, 992, 8145, 73665, 725630, 7840280, 92297011, 1176802235, 16129154724, 236335661166, 3685509077329, 60981635041557

Offset: 2

Hugo Pfoertner, Jan 09 2022

There are six places in the Algol 60 procedure mergesort where the keys are compared. 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.
.
   n  Worst case
   |  A350567(n)
   |   |  Average
   |   |  a(n)/n!
   |   |    |    Average/
   |   |    |   (n*log(n))
   2   1   1.000  0.721
   3   4   3.167  0.961
   4   6   5.417  0.977
   5  10   8.267  1.027
   6  13  11.313  1.052
   7  17  14.616  1.073
   8  20  17.997  1.082
   9  25  21.606  1.093
  10  29  25.435  1.105
  11  34  29.481  1.118
  12  38  33.672  1.129
  13  43  37.953  1.138
  14  47  42.276  1.144
  15  52  46.634  1.148

D. E. Knuth, The Art of Computer Programming Second Edition. Vol. 3, Sorting and Searching. Chapter 5.2.4 Sorting by Merging, Pages 164-166. Addison-Wesley, Reading, MA, 1998.

A. D. Woodall, An internal sorting procedure using a two-way merge, Algorithm 45, The Computer Journal, Volume 13, Number 1, February 1970, Algorithms Supplement, pp. 110-111.

Cf. A001768, A001855, A350567, A350569.

A350660 a(n) is the average number of key comparisons, rounded to the nearest integer, required to sort n records with distinct keys using bubble sort (Algorithm B in Don Knuth's TAOCP Vol. 3).

Original entry on oeis.org

1, 3, 5, 9, 13, 18, 24, 31, 39, 48, 58, 69, 80, 93, 107, 121, 137, 153, 171, 189, 209, 229, 251, 273, 297, 321, 346, 373, 400, 428, 458, 488, 519, 551, 584, 619, 654, 690, 727, 765, 804, 845, 886, 928, 971, 1015, 1060, 1106, 1153, 1201, 1250, 1300, 1351, 1403

Offset: 2

Hugo Pfoertner, Feb 01 2022

nonn

			        n        b(n)
        |         |         a(n)=
        |         |      round(b(n))
        |         |           |   b(n)/n^2
        2        1/1          1   0.2500
        3        8/3          3   0.2963
        4       31/6          5   0.3229
        5      128/15         9   0.3413
        6     1151/90        13   0.3552
        7    11309/630       18   0.3663
        8    17303/720       24   0.3755
        9  1408073/45360     31   0.3832
       10  2526503/64800     39   0.3899
      100                  4768   0.4768
     1000                496458   0.4965
    10000                         0.4995
   100000                         0.4999
  1000000                         0.5000

D. E. Knuth, The Art of Computer Programming Second Edition. Vol. 3, Sorting and Searching. Chapter 5.2.2 Sorting by Exchanging, pages 106-109, 128-130. Addison-Wesley, Reading, MA, 1998.

Cf. A001620, A190186, A190187, A190194, A350428, A350568, A350569.

a(n) = round(b(n)).
b(n) = binomial(n+1,2) - A190186(n)/A190187(n).
b(n) = binomial(m,2) - ((m/2)*(log(m) + gamma +log(2)) - 2*sqrt(2*Pi*m)/3 + 49/36 + O(n^(-1/2))) with gamma = A001620, and m = n + 1 (Knuth's asymptotic formula (37), TAOCP vol. 3, page 130).
a(n)/n^2 -> 1/2 for n -> infinity.

cp's OEIS Frontend

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).

Views

Author

Keywords

Comments

References

Crossrefs

A350426 a(n) is the maximum number of key comparisons required to sort n records with distinct keys using heapsort (Algorithm H in Don Knuth's TAOCP Vol. 3).

Views

Author

Keywords

Comments

References

Crossrefs

A350427 a(n) is the maximum 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).

Views

Author

Keywords

Comments

References

Crossrefs

A350567 a(n) is the maximum number of key comparisons required to perform an indirect sort of n records with distinct keys using a two-way merge (A. D. Woodall's mergesort).

Views

Author

Keywords

Comments

References

Links

Crossrefs

A350568 a(n)/n! is the average number of key comparisons required to perform an indirect sort of n records with distinct keys using a two-way merge (A. D. Woodall's mergesort).

Views

Author

Keywords

Comments

References

Links

Crossrefs

A350660 a(n) is the average number of key comparisons, rounded to the nearest integer, required to sort n records with distinct keys using bubble sort (Algorithm B in Don Knuth's TAOCP Vol. 3).

Views

Author

Keywords

Examples

References

Crossrefs

Formula