1

Cormen's Algorithm book(CLRS) のクイック ソート アルゴリズムを実装しています。

 vector<int> numbers = {5, 6, 3, 4, 1, 2, 7, 13, -6, 0, 3, 1, -2};

 My_Quick_Sort(numbers.begin(), numbers.end());

エラーはありませんが、数字を並べ替えることができません。

本にある疑似コードは以下のようなものです。

  1. クイックソート(A, p, r)
  2. p < rの場合
  3. q = パーティション (A、p、r)
  4. クイックソート(A, p, q-1)

  5. クイックソート(A, q+1, r)

  6. パーティション(A、p、r)

  7. x = A[r]
  8. i = p - 1
  9. j = p から r - 1 の場合
  10. _ _ _i= i+1;
  11. _ _ _交換 A[i] と A[j]
  12. A[i+1] を A[r] と交換する
  13. i + 1 を返します。

私の実装は次のようなものです。

 template<typename T>
 void Swap(T a, T b)
 {
     typedef typename std::iterator_traits<T>::value_type value_type;
     value_type temp;
     temp = *a;
     *a = *b;
     *b = temp;
 }

 template<typename T>
 int Partition(T begin, T end)
 {
     typedef typename std::iterator_traits<T>::value_type value_type;
     value_type x;
         x = *end;
     T i = begin - 1;
     T j;
     for(j = begin; j != end+1; ++j)
     {
         if ( x >= *j )
         {
              i++;
              Swap(i, j);
         }
         Swap(i+1, end);
     }
     return static_cast<int>(distance(begin, i) + 1);
 }

 template<typename T>
 void Q_Sort(T begin, T end)
 {
     auto length = end - begin;
     if (length < 2) return;

     if ( begin != end )
     {
         auto pivot = Partition(begin, end);
         Q_Sort(begin, begin + pivot - 1);
         Q_Sort(begin + pivot + 1, end);
     }
 }

誰かが私のコードについて何か知っていますか? 動作しますが、ソートはしません。たとえば、シャッフルを入力した場合: 13, 0, -6, 6, -2, 5, 4, 3, 1, 1, 3, 2, 7,

出力は My_Quick_Sort のようになります: -6, -2, 0, 6, 13, 0, 5, 1, 1, 4, 2, 3, 7,

4

2 に答える 2

1

ほとんどの場合、quicksort() アルゴリズムが失敗しますが、圧倒的な原因はパーティション アルゴリズムであり、ピボット スロットを適切に除外できていないか、下位側と上位側の計算が正しくありません。これも例外ではありません。インプレース パーティショニングを行うライブの例をご覧ください。

あなたの場合、あなたのパーティションアルゴリズムは、パーティション化されている領域がbegin要素で始まり、要素で終わると仮定することを保証します。言い換えればend、これ:

for(j = begin; j != end+1; ++j)

これである必要があります：

for(j = begin; j != end; ++j)

失敗した quicksort() の 2 番目の圧倒的な原因は、前回のパーティショニングの実行からピボットだけをスキップできなかったことです。前のコードで述べた正しいことを行うと、次のようになります。

 auto pivot = Partition(begin, end);
 Q_Sort(begin, begin + pivot - 1);  // <<=== -1 should not be here.
 Q_Sort(begin + pivot + 1, end);

実際にはこれでなければなりません：

 auto pivot = Partition(begin, end);
 Q_Sort(begin, begin + pivot);
 Q_Sort(begin + pivot + 1, end);

C++ イテレータは に実行されることを思い出してください。これは、必要な最後の要素の次end()の最初の要素であるため、-1 は必要ありません。のようなシーケンスが与えられます。

int ar[] = { 5,6,2,7,9,8 }

ピボット スロットが 4 番目のスロット (pivot=3) にあるとします。

 Q_Sort(begin, begin + pivot);    // includes 5,6,2, NOT 7
 Q_Sort(begin + pivot + 1, end);  // includes 9,8, again, NOT 7

奇妙に思えるかもしれませんが、誤ってピボット スロットをスキップしたくない場合、呼び出しは次のようになります。

 Q_Sort(begin, begin + pivot);   // beginning through (pivot-1)
 Q_Sort(begin + pivot, end);     // pivot through end

これは、quicksort() の実装でよくあるもう 1 つの間違いです。

これらの基本に取り組んでください。そうすれば、うまくいくはずです。

于 2013-08-10T12:50:29.960 に答える
1

実装に関するいくつかの注意事項:

まず、Q_Sort メソッドとロジックを単純化するために、int ではなくパーティション メソッドからイテレータを返します。これにより、以下のように Q_Sort が簡素化されます。

template<typename T>
void Q_Sort(T begin, T end)
{
    if ( begin < end )
    {
        T pivot = Partition(begin, end);
        Q_Sort(begin, pivot - 1);
        Q_Sort( pivot + 1, end);
    }
}

「if (length < 2) return;」のチェックは必要ありませんのでご注意ください。

次に、 for ループのパーティション メソッドで、終了条件 "j != end+1" が疑似コードと一致しません。end - 1 である必要があります。Partition メソッドの新しいコードを次に示します。2 番目のパラメーター (end) が最後の値を指すのではなく、実際の最後の値を指すと想定していることに注意してください。

template<typename T>
T Partition(T begin, T end)
{
    typedef typename std::iterator_traits<T>::value_type value_type;
    value_type x;

    x = *end;
    T i = begin - 1;

    for(T j = begin; j < end; ++j)
    {
        if ( x >= *j )
        {
            i++;
            Swap(i, j);
        }
    }

    Swap(i+1, end);
    //return static_cast<int>(distance(begin, i) + 1);
    return i+1;
}

最後に、疑似コードは 2 番目のパラメーターが最後の要素であると想定していますが、反復子 numbers.end() は最後の要素を超えた位置を指しています。したがって、以下のように呼び出しをクイックソートに変更する必要があります。

vector<int>::iterator iterEnd = numbers.end();
--iterEnd;
Q_Sort(numbers.begin(), iterEnd);

上記の点を考慮した後、正しくソートできるはずです。

于 2013-08-10T12:18:37.780 に答える