|
|
A334750
|
|
Total number of swaps needed to sort all n! permutations of n elements by the optimal dual-pivot quicksort "Count".
|
|
0
|
|
|
0, 0, 4, 16, 103, 711, 5526, 48066, 463248, 4908816, 56749536, 711299232, 9609618816, 139252708224, 2154724104960, 35464952597760, 618712803717120, 11405648080834560, 221541001069731840, 4522678391979417600, 96811891510299033600, 2168416142767145779200
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
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
|
|
|
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).]
|
|
PROG
|
(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); };
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|