部分的にソートされたクイックソート

Question

クイックソートを変更して、トップメジアンアイテムのみをソートする場所に変更したい。 そのように[9 5 7 1 2 4 6]と設定すると、5が中央値である場合、部分的にソートされたセットは[1 2 4 5 9 6 7]のようになります。

私は（あなたがいずれかを知っていれば、私は、任意の他の良い動画をお知らせ！）mycodeschoolでユーチューブにクイックソートの分析を見てきました

template <class Comparable> 
void objectSwap(Comparable &lhs, Comparable &rhs) { 
    Comparable tmp = lhs; 
    lhs = rhs; 
    rhs = tmp; 
} 

template <class Comparable> 
void choosePivot(vector<Comparable> &a, int first, int last) { 
    int middle = (first + last)/2; 
    objectSwap(a[first], a[middle]); 
} 

template <class Comparable> 
void partition(vector<Comparable> &a, int first, int last, int &pivotIndex) { 
    // place the pivot in a[first] 
    choosePivot(a, first, last); 
    Comparable pivot = a[first]; 
    int lastS1 = first; 
    int firstUnknown = first + 1; 

    for (; firstUnknown <= last; ++firstUnknown) { 
     if (a[firstUnknown] < pivot) { 
      ++lastS1; 
      objectSwap(a[firstUnknown], a[lastS1]); 
     } 
     // else item from unknown belongs in S2 
    } 
    // decide a new pivot 
    objectSwap(a[first], a[lastS1]); 
    pivotIndex = lastS1; 
} 

template <class Comparable> 
void partialsort(vector<Comparable> &a, int first, int last) { 
    int pivotIndex; 

    if (first < last) { 
     partition(a, first, last, pivotIndex); 
     partialsort(a, first, pivotIndex - 1); 
     partialsort(a, pivotIndex + 1, last); 
    } 
} 

template <class Comparable> 
void partialsort(vector<Comparable> &a) { 
    partialsort(a, 0, a.size() - 1); 
} 

、と私は私だけpartialsortを変更する必要があります確信しています（vector、int、int）メソッドです。
最初の反応は、mergesortのように考えて、空の配列をとり、長さ/ 2が満たされたらアルゴリズムを停止することです。しかし、私はそれがクイックソートの仕組みではないことを知っています。すべての再帰呼び出しと、最初、最後、およびピボットが常に変化するため、何が起こっているのかを追跡することが難しくなります。私は中央値をいつどのように知っているかもわかりません。 これは宿題の質問です。誰かがクイックソートの理解に役立つこの資料やリソースにどのようにアプローチすべきかについてのヒントがあれば、大変感謝しています。それを変更する方法を知っているだけで、アルゴリズムの理解を深めることはできません。
申し訳ありませんが、私はどんな種類の助けを欲しいのですか？

Answer 1

それは分割統治アルゴリズムですので、あなたは完全に前半がソートされると、自然に中央値を保持する配列の中間位置、後ろにある任意のパーティションをスキップすることができます。