login
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

%I #11 Feb 02 2022 07:25:36

%S 1,3,5,9,13,18,24,31,39,48,58,69,80,93,107,121,137,153,171,189,209,

%T 229,251,273,297,321,346,373,400,428,458,488,519,551,584,619,654,690,

%U 727,765,804,845,886,928,971,1015,1060,1106,1153,1201,1250,1300,1351,1403

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

%D 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.

%F a(n) = round(b(n)).

%F b(n) = binomial(n+1,2) - A190186(n)/A190187(n).

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

%F a(n)/n^2 -> 1/2 for n -> infinity.

%e n b(n)

%e | | a(n)=

%e | | round(b(n))

%e | | | b(n)/n^2

%e 2 1/1 1 0.2500

%e 3 8/3 3 0.2963

%e 4 31/6 5 0.3229

%e 5 128/15 9 0.3413

%e 6 1151/90 13 0.3552

%e 7 11309/630 18 0.3663

%e 8 17303/720 24 0.3755

%e 9 1408073/45360 31 0.3832

%e 10 2526503/64800 39 0.3899

%e 100 4768 0.4768

%e 1000 496458 0.4965

%e 10000 0.4995

%e 100000 0.4999

%e 1000000 0.5000

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

%K nonn

%O 2,2

%A _Hugo Pfoertner_, Feb 01 2022