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

<p>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. </p>

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

CC BY-SA 3.0
2016-05-06T09:24:30.507Z
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)
László Kozma
CC BY-SA 3.0
2016-05-11T02:57:07.080Z
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.
shaunc
<sorting><metrics>
Quicksort optimal partition
shaunc
# Quicksort optimal partition

(Asked by: username_0 on 2016-04-29)

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?

**Tags:** sorting, metrics
> **Comments:**
> **username_1**: 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)  
> **username_0**: 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.  

---

## 0 answers

