2
$\begingroup$

I'm studying a variation of Quicksort in which the algorithm samples a subarray of size $f(n)< n$ ($n$ is the size of the input array) and then chooses the pivot from this subarray. The pivot is accepted if it lies in the middle third of the sampled array, otherwise it is rejected and the subarray is sampled again until the pivot is accepted. Is there any reference in which this variation has been studied?

$\endgroup$
1
  • $\begingroup$ If you sample a subarray, it does not make much sense to "just" choose a single pivot and divide the array in two parts according to this single pivot. Rather, you can take advantage of the elements accessed to partition the array into $f(n)+1$ blocks by 1) sorting the $f(n)$ elements) and partition the $n$ elements according to those. $\endgroup$
    – J..y B..y
    Nov 21 at 10:18

1 Answer 1

1
$\begingroup$

Sebastian Wyld from the University of Liverpool has been extensively working on the analysis of various versions of QuickSort: His 2016 thesis, "Dual-Pivot Quicksort and Beyond: Analysis of Multiway Partitioning and Its Practical Potential", explored the analysis of the complexity of "Multiway Quicksort, i.e., partitioning the input in one step around several pivots" and includes

Sebastian is very kind, and if you have questions about his work (after studying it seriously), I do believe that he would answer any question you may have.

I hope it helps!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.