Mean-of-2-4 Quicksort

Abstract

By combining the Median-of-three and Regrouping-3 quicksort methods, the Joint quicksort is proposed, largely free from the shortcomings of the first two. For example, the time complexity of Joint quicksort, in case of lists of n equal elements, is O(n). Analysis of the dependence of Quicksort time complexity on the ratio of the derived sublist sizes shows a relatively slow increase in sorting time as the ratio in question decreases from 0.5 to 0.1. The proposed category of Mean-of-K (MeK) sorting algorithms provides for the determination of pivot elements as the mean of K elements. It is shown that, in terms of sorting time, at K ∈ [1, 4] and size r of the list/sublist of elements to be sorted, it is convenient to use (roughly): Insertion sort at r ≤ 9, Me2 quicksort at 10 ≤ r ≤ 21, Me3 quicksort at 22 ≤ r ≤ 46, and Me4 quicksort at r > 46, yielding the Mean-of-2-4 quicksort method. It was found that the determination of pivot elements in the Median-of-three method requires more calculations than in the Mean-of-3 method; respectively, using Mean-of-3 method could also reduce sorting time. Of course, Mean-of-2-4 method could reduce this duration even further.

Combinând metodele de sortare rapidă Mediana-a-trei și Regrupare-3, este propusă sortarea rapidă Îmbinată, lipsită în mare măsură de neajunsurile primelor două. De exemplu, complexitatea temporală a sortării rapide îmbinate, în cazul unor liste din n elemente egale, este O(n). Analiza dependenței duratei sortării Rapide de raportul dintre dimensiunile sublistelor derivate arată la o creștere relativ lentă a duratei sortării cu micșorarea raportului în cauză de la 0,5 șa 0,1. Categoria de algoritmi de sortare Media-a-K (MeK) propusă prevede determinarea elementelor pivot ca media a K elemente. Este demonstrat că, în ce privește durata sortării, la K ∈ [1, 4] și dimensiunea r a listei/sublistei de elemente de sortat, este oportun de folosit (aproximativ): sortarea prin Inserție la r ≤ 9, sortarea Me2 la 10 ≤ r ≤ 21, sortarea Me3 la 22 ≤ r ≤ 46 și sortarea Me4 la r > 46, obținând astfel metoda de sortare rapidă Media-a-2-4. S-a constatat că determinarea elementelor pivot la metoda Mediana-a-trei necesită mai multe calcule decât la metoda Media-a-3; respectiv, folosirea metodei Media-a-3 ar putea reduce și durata sortării. Bineînțeles, metoda Media-a-2-4 ar putea reduce această durată și mai mult.