|
%I #45 Feb 03 2018 12:54:11
%S 0,0,2,16,112,848,7032,64056,639888,6974928,82531296,1054724256,
%T 14487894144,212971227264
%N Number of key comparisons to sort all n! permutations of n elements by the optimal trial-pivot quicksort.
%C 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.
%H M. Aumüller and M. Dietzfelbinger, <a href="https://doi.org/10.1145/2963102">How Good Is Multi-Pivot Quicksort?</a>, ACM Transactions on Algorithms (TALG), Volume 13 Issue 1, 2016.
%H M. Aumüller and M. Dietzfelbinger, <a href="https://arxiv.org/abs/1510.04676">How Good Is Multi-Pivot Quicksort?</a>, arXiv:1510.04676 [cs.DS], 2016.
%H Daniel Krenn, <a href="https://github.com/dkrenn/quickstar">Quickstar</a>, Program in SageMath, on GitHub.
%H <a href="/index/So#sorting">Index entries for sequences related to sorting</a>.
%Y Cf. A001768, A003070, A036604, A117627, A117628, A159324, A288964, A288965, A288971.
%K nonn,more
%O 0,3
%A _Daniel Krenn_, Jun 20 2017
%E a(9)-a(11) from _Melanie Siebenhofer_, Jan 29 2018
%E a(12)-a(13) from _Melanie Siebenhofer_, Feb 02 2018
|
