A117628 -id:A117628 - cp's OEIS frontend

A288964 Number of key comparisons to sort all n! permutations of n elements by quicksort.

0, 0, 2, 16, 116, 888, 7416, 67968, 682272, 7467840, 88678080, 1136712960, 15655438080, 230672171520, 3621985113600, 60392753971200, 1065907048550400, 19855856150323200, 389354639411404800, 8017578241634304000, 172991656889856000000, 3903132531903897600000

Offset: 0

Daniel Krenn, Jun 20 2017

nonn

From Petros Hadjicostas, May 04 2020: (Start)
Depending on the assumptions used in the literature, the average number to sort n items in random order by quicksort appears as -C*n + 2*(1+n)*HarmonicNumber(n), where C = 2, 3, or 4. (To get the number of key comparisons to sort all n! permutations of n elements by quicksort, multiply this number by n!.)
For this sequence, we have C = 4. The corresponding number of key comparisons to sort all n! permutations of n elements by quicksort when C = 3 is A063090(n). Thus, a(n) = A063090(n) - n!*n.
For more details, see my comments and references for sequences A093418, A096620, and A115107. (End)

Daniel Krenn, Table of n, a(n) for n = 0..100
Pamela E. Harris, Jan Kretschmann, and J. Carlos Martínez Mori, Lucky Cars and the Quicksort Algorithm, arXiv:2306.13065 [math.CO], 2023.
Index entries for sequences related to sorting

Cf. A063090, A093418, A096620, A115107, A117627, A117628, A159324, A288965.

a:= proc(n) option remember; `if`(n<3, n*(n-1),
      ((2*n^2-3*n-1)*a(n-1)-(n-1)^2*n*a(n-2))/(n-2))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Jun 21 2017

a[n_] := n! (2(n+1)HarmonicNumber[n] - 4n);
a /@ Range[0, 25] (* Jean-François Alcover, Oct 29 2020 *)

[n.factorial() * (2*(n+1)*sum(1/k for k in srange(1, n+1)) - 4*n) for n in srange(21)]

# alternative using the recurrence relation
@cached_function
def c(n):
    if n <= 1:
        return 0
    return (n - 1) + 2/n*sum(c(i) for i in srange(n))
[n.factorial() * c(n) for n in srange(21)]

a(n) = n!*(2*(n+1)*H(n) - 4*n).
c(n) = a(n) / n! satisfies c(n) = (n-1) + 2/n * Sum_{i < n} c(i).
a(n) = 2*A002538(n-1), n >= 2. - Omar E. Pol, Jun 20 2017
E.g.f.: -2*log(1-x)/(1-x)^2 - 2*x/(1-x)^2. - Daniel Krenn, Jun 20 2017
a(n) = ((2*n^2-3*n-1)*a(n-1) -(n-1)^2*n*a(n-2))/(n-2) for n >= 3, a(n) = n*(n-1) for n < 3. - Alois P. Heinz, Jun 21 2017
From Petros Hadjicostas, May 03 2020: (Start)
a(n) = A063090(n) - n!*n for n >= 1.
a(n) = n!*A115107(n)/A096620(n) = n!*(-n + A093418(n)/A096620(n)). (End)

A288970 Number of key comparisons to sort all n! permutations of n elements by the optimal trial-pivot quicksort.

Original entry on oeis.org

0, 0, 2, 16, 112, 848, 7032, 64056, 639888, 6974928, 82531296, 1054724256, 14487894144, 212971227264

Offset: 0

Daniel Krenn, Jun 20 2017

The 3 pivot elements are chosen from fixed indices (e.g., the last 3 elements). The "optimal" strategy minimizes, after the choice of the pivots is done, the expected partitioning cost.

M. Aumüller and M. Dietzfelbinger, How Good Is Multi-Pivot Quicksort?, ACM Transactions on Algorithms (TALG), Volume 13 Issue 1, 2016.
M. Aumüller and M. Dietzfelbinger, How Good Is Multi-Pivot Quicksort?, arXiv:1510.04676 [cs.DS], 2016.
Daniel Krenn, Quickstar, Program in SageMath, on GitHub.
Index entries for sequences related to sorting.

Cf. A001768, A003070, A036604, A117627, A117628, A159324, A288964, A288965, A288971.

a(9)-a(11) from Melanie Siebenhofer, Jan 29 2018

a(12)-a(13) from Melanie Siebenhofer, Feb 02 2018

A117627 Let f(n) = minimum of average number of comparisons needed for any sorting method for n elements and let g(n) = n!*f(n). Sequence gives a lower bound on g(n).

Original entry on oeis.org

0, 2, 16, 112, 832, 6896, 62368, 619904, 6733312, 79268096, 1010644736, 13833177088, 203128772608, 3175336112128, 52723300200448, 927263962759168, 17221421451378688, 336720980854571008, 6911300635636400128, 148661140496700932096

Offset: 1

N. J. A. Sloane, Oct 06 2006

nonn

Sorting methods have been constructed such that the lower bound of f(n) is achieved for n=1, 2, 3, 4, 5, 6, 9 and 10. Y. Césari was the first to show that f(7) is not obtainable. He also constructed optimal solutions for n=9 and 10. L. Kollár showed that the minimum number of comparisons needed for n=7 is 62416. - Dmitry Kamenetsky, Jun 11 2015

Y. Césari, Questionnaire codage et tris, PhD Thesis, University of Paris, 1968.
D. E. Knuth, TAOCP, Vol. 3, Section 5.3.1.

Alois P. Heinz, Table of n, a(n) for n = 1..450
L. Kollár, Optimal sorting of seven element sets, Proceedings of the 12th symposium on Mathematical foundations of computer science 1986, 449-457.
Index entries for sequences related to sorting

Cf. A003070, A036604, A117628.

q:= n-> ceil(log[2](n!)):
a:= n-> (q(n)+1)*n! - 2^q(n):
seq(a(n), n=1..30);  # Alois P. Heinz, Jun 11 2015

q[n_] := Log[2, n!] // Ceiling; a[n_] := (q[n]+1)*n! - 2^q[n]; Array[a, 20] (* Jean-François Alcover, Feb 13 2016 *)

a(n) = { my(N=n!, q = ceil(log(N)/log(2))); return ((q+1)*N - 2^q);} \\ Michel Marcus, Apr 21 2013

Knuth gives an explicit formula.

a(n) = (q(n)+1)*n! - 2^q(n) with q(n) = A003070(n).

cp's OEIS Frontend

A288964 Number of key comparisons to sort all n! permutations of n elements by quicksort.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

SageMath

SageMath

Formula

A288970 Number of key comparisons to sort all n! permutations of n elements by the optimal trial-pivot quicksort.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A117627 Let f(n) = minimum of average number of comparisons needed for any sorting method for n elements and let g(n) = n!*f(n). Sequence gives a lower bound on g(n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula