|
|
A288971
|
|
Number of key comparisons to sort all n! permutations of n elements by the optimal quadral-pivot quicksort.
|
|
13
|
|
|
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
|
Daniel Krenn, Quickstar, Program in SageMath, on GitHub.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|