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

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,2

References

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.

Links

Table of n, a(n) for n=2..55.

Formula

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.

Example

        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

Crossrefs

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

Sequence in context: A024403 A129230 A203567 * A071404 A074133 A215909

Adjacent sequences: A350657 A350658 A350659 * A350661 A350662 A350663

Keyword

nonn

Author

Hugo Pfoertner, Feb 01 2022

Status

approved