A334750 Total number of swaps needed to sort all n! permutations of n elements by the optimal dual-pivot quicksort "Count".

0, 0, 4, 16, 103, 711, 5526, 48066, 463248, 4908816, 56749536, 711299232, 9609618816, 139252708224, 2154724104960, 35464952597760, 618712803717120, 11405648080834560, 221541001069731840, 4522678391979417600, 96811891510299033600, 2168416142767145779200

Offset: 0

Author

Petros Hadjicostas, May 09 2020

Keywords

• nonn

Comments

The dual-pivot quicksort "Count" differs slightly from the original version of the dual-pivot quicksort algorithm of Aumüller et al. (2016, 2019). See Algorithm 1 in Neininger and Straub (2017, 2018).

By the design of the algorithm, for n >= 2, Neininger and Straub always require at least two swaps "at the end in order to bring the [two] pivots to their final positions".

Here a(n) is n! times the average number of swaps of the dual-pivot quicksort "Count" when sorting a random permutation of length n.

Links

• M. Aumüller, M. Dietzfelbinger, C. Heuberger, D. Krenn, and H. Prodinger, Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths, arXiv:1611.00258 [math.CO], 2016.
• M. Aumüller, M. Dietzfelbinger, C. Heuberger, D. Krenn, and H. Prodinger, Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths, Combin. Probab. Comput. 28(4) (2019), 485-518.
• R. Neininger and J. Straub, Probabilistic analysis of the dual-pivot quicksort "count", arXiv:1710.07505 [cs.DS], 2017.
• R. Neininger and J. Straub, Probabilistic analysis of the dual-pivot quicksort "count", 2018 Proceedings of the Meeting of Analytic Algorithmics and Combinatorics, New Orleans, Louisiana, USA, 7pp.

Crossrefs

Cf. A058312, A058313, A288964, A288965, A288970, A288971.

Programs

PARI

lista(nn) = { nn = max(nn, 3); my(va = vector(nn)); va[1] = 0; va[2] = 4; for(n=3, nn, va[n] = n!*(6*sum(k=1, n-2, (n-k-1)*va[k]/k!)/(n*(n-1)) + 5*n/8 + 13/16 - 1/(16*(n - (1 + (-1)^n)/2)))); concat(0, va); };

PARI

H1(n) = sum(k=1, n, 1/k);
H2(n) = sum(k=1, n, (-1)^k/k);
H3(n) = if(0 == (n % 2), - (1/320)*(1/(n - 3) + 3/(n - 1)), (1/320)*(3/(n - 2) + 1/n));
lista(nn) = { nn = max(nn, 3); my(va = vector(nn)); va[1] = 0; va[2] = 4; va[3] = 16; for(n=4, nn, va[n] = n!*((3/4)*n*H1(n) + (1/20)*n*H2(n) - (4/5)*n + (3/4)*H1(n) + (1/20)*H2(n) - 23/160 - (-1)^n/40 + H3(n))); concat(0,va); };

Formula

Recurrence: a(n)/n! = (6/(n*(n - 1)))*(Sum_{k=0..n-2} (n - k - 1)*a(k)/k!) + 5*n/8 + 13/16 - 1/(16*(n - I[n is even])) for n >= 2 with a(0) = a(1) = 0, where I(condition) = 1 if the condition holds, and = 0 otherwise. [See p. 7 in Neininger and Straub (2017).]

a(n) = n!*((3/4)*n*Harmonic(n) + (1/20)*n*Harmonic_alt(n) - (4/5)*n + (3/4)*Harmonic(n) + (1/20)*Harmonic_alt(n) - 23/160 - (-1)^n/40 - ([n even]/320)*(1/(n - 3) + 3/(n - 1)) + ([n odd]/320)*(3/(n - 2) + 1/n)) for n >= 4, where Harmonic_alt(n) = Sum_{k=1..n} (-1)^n/n = -A058313(n)/A058312(n). [See Theorem 2.1 in Neininger and Straub (2017, 2018).]