DSpace Repository

Mean-of-2-4 Quicksort

Show simple item record

dc.contributor.author BOLUN, Ion
dc.date.accessioned 2024-05-21T09:31:42Z
dc.date.available 2024-05-21T09:31:42Z
dc.date.issued 2024
dc.identifier.citation BOLUN, Ion. Mean-of-2-4 quicksort. In: Journal of Engineering Science. 2024, vol. 31, nr. 1, pp. 18-33. ISSN 2587-3474, eISSN 2587-3482. en_US
dc.identifier.issn 2587-3474
dc.identifier.issn 2587-3482
dc.identifier.uri https://doi.org/10.52326/jes.utm.2024.31(1).02
dc.identifier.uri http://repository.utm.md/handle/5014/27163
dc.description.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. en_US
dc.description.abstract 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. en_US
dc.language.iso en en_US
dc.publisher Technical University of Moldova en_US
dc.relation.ispartofseries Journal of Engineering Science;2024, vol. 31, nr. 1
dc.rights Attribution-NonCommercial-NoDerivs 3.0 United States *
dc.rights.uri http://creativecommons.org/licenses/by-nc-nd/3.0/us/ *
dc.subject basic quicksort en_US
dc.subject algoritms en_US
dc.subject sortare rapidă îmbinată en_US
dc.subject algoritmi en_US
dc.title Mean-of-2-4 Quicksort en_US
dc.title.alternative Sortarea rapidă media-a-2-4 en_US
dc.type Article en_US


Files in this item

The following license files are associated with this item:

This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivs 3.0 United States Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 United States

Search DSpace


Advanced Search

Browse

My Account