Has the question been studied, how to find the shortest sequence of partition choices so that a quick-sort algorithm can sort a set?

To be clear, I'm not interested in quick sort per se, but in constructing a measure of difference between two sets (of equal size), the elements of both of which have been assigned integer ranks. I'd like a measure of what is the minimum effort to to transform the order of one set into that of the the other using a quick sort-like procedure; presumably assuming one set has already been sorted is a harmless simplification of the problem.

Is there a known algorithm w/ asymptotic time bound to compute the shortest partition sequence?

  • $\begingroup$ Can you clarify a bit what you mean by "shortest sequence of partition choices"? Do you mean the choice of pivot for every recursive call in Quicksort? Is the measure you are looking for "the minimum cost of Quicksort, over all possible choices of pivots", for a given permutation? (or in other words: the cost of Quicksort with the most favorable sequence of pivot choices) $\endgroup$ – László Kozma May 6 '16 at 9:24
  • $\begingroup$ Good question. I do mean choice of pivot for every recursive call. Perhaps best to call this a tree rather than a sequence; I'm asking about an algorithm to minimize the total number of nodes in that tree. I believe this to be equivalent to your other formulations. $\endgroup$ – shaunc May 11 '16 at 2:57

Your Answer

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

Browse other questions tagged or ask your own question.