login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A288971 Number of key comparisons to sort all n! permutations of n elements by the optimal quadral-pivot quicksort. 11
0, 0, 2, 16, 112, 848, 7008, 63648, 635040, 6915168, 81757440, 1044161280, 14334076800, 210595524480 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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

LINKS

Table of n, a(n) for n=0..13.

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.

CROSSREFS

Cf. A288964, A288965, A288970.

Sequence in context: A058121 A117627 A117628 * A288970 A037564 A125725

Adjacent sequences:  A288968 A288969 A288970 * A288972 A288973 A288974

KEYWORD

nonn,more

AUTHOR

Daniel Krenn, Jun 20 2017

EXTENSIONS

a(9)-a(13) from Melanie Siebenhofer, Feb 05 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 4 04:39 EDT 2020. Contains 334815 sequences. (Running on oeis4.)