MEAN-OF-2-4 QUICKSORT

Authors

DOI:

https://doi.org/10.52326/jes.utm.2024.31(1).02

Keywords:

basic Quicksort, Median-of-three quicksort, Regrouping-3 quicksort, pivot element determination, time complexity, algorithm comparison

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.

Downloads

Published

2024-03-31

How to Cite

Bolun, I. (2024). MEAN-OF-2-4 QUICKSORT. JOURNAL OF ENGINEERING SCIENCE, 31(1), 18–33. https://doi.org/10.52326/jes.utm.2024.31(1).02