6

クイック ソート アルゴリズムのこの素晴らしい視覚化を見ました: http://www.youtube.com/watch?v=Z5nSXTnD1I4

クイック ソートの背後にある原則を本当に理解していると感じ、オンラインのガイドの助けを借りて、独自のクイック ソートの作成に取り掛かりました。
これは私が思いついたものです：

public void quickSort(int[] a, int left, int right) {

    int index = partition(a, left, right);
    if (left < index - 1)
      quickSort(a, left, index);
    if (index < right)
      quickSort(a, index + 1, right);
}

private int partition (int[] a, int left, int right) {
    int i = left - 1;
    int j = right + 1;
    int pivot = a[0];

    while (i < j) {

        i++;

        while (a[i] < pivot)
            i++;

        j--;

        while (a[j] > pivot)
            j--;

        if (i < j)
            swap (a, i, j);
    }
return i;
}   

private void swap (int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

left と right の値は次のとおりです。

left = 0
right = array size - 1

残念ながら、出力は正しくありません。問題は、ピボットの扱いにあるようです。私が見たビジュアライゼーションでは、インストラクターはピボットを物理的に削除し、ポインターを何も指さないようにしました。彼はチュートリアルを続け、i と j (私は左右と呼んでいます) が両方とも同じ空の場所を指しているポイントに到達したとき、彼はピボットを挿入して続行しました。

私は物理的にピボットを所定の位置に保持しているため、適切にソートするのが難しいと感じています.

このコードでは、次の入力を使用しています。

4 8 1 6 3 7 2 5

出力が得られます：

1 3 2 6 8 7 4 5

「4」の値 (つまり、ピボット) がアルゴリズムの開始時にソートされると、私はそれを再利用することはありません。また、quickSort メソッドに問題があると思います。

誰かが私にいくつかの指針を教えてもらえますか？ありがとう。

編集: ここにあった 2 つの編集は、不要で不正確な情報が含まれていたため削除されました。そのうちの 1 人は、ピボットを (左 + 右) / 2 に変更しました。これは、以下の回答で説明されている理由から、もちろん間違っていました。

4

4 に答える 4

4

と の両方が必要なため、パーティションを削除する必要がiありjました。次のようになります。

public void quickSort(int[] a, int left, int right) {

    int i = left; // Was -1 
    int j = right; // Was +1
    int pivot = a[left + (right - left) / 2]; // Pivot is the value of the middle index, not the index itself
    while (i <= j) { // Changed terminating condition
        //   i++;  Not needed
        while (a[i] < pivot) { 
            i++;
        }
        //    j++; Not needed
        while (a[j] > pivot) {
            j--;
        }
        if (i <= j) {  // Changed terminating condition
            swap(a, i, j);
            i++;  // You need to progress the indexes after the swap
            j--;
        }
    }

    System.out.println(Arrays.toString(a));
    if (left < j) {  // Changed condition
        quickSort(a, left, j);
    }
    if (i < right) { 
        quickSort(a, i, right); // was i + 1
    }
}

出力：

[4, 5, 1, 2, 3, 7, 6, 8]
[1, 5, 4, 2, 3, 7, 6, 8]
[1, 3, 2, 4, 5, 7, 6, 8]
[1, 2, 3, 4, 5, 7, 6, 8]
[1, 2, 3, 4, 5, 7, 6, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
于 2013-02-23T21:47:23.170 に答える
2 
int pivot = a[0];

する必要があります

int pivot = a[left];

それを に変更swap (a, i, j);するswap (a, i--, j++);と、すべてが正常に動作するように見えます。

上記の変更の理由:

ピボットは、最初の要素ではなく、範囲内の最初の要素である必要があります。

次のように、この中間であってはなりません。

int pivot = a[(left + right) / 2];

どの要素をピボットにするかは問題ではありません。最も簡単なのは、選択した要素を常に最初の要素と交換し、通常どおり続行することです。他の方法もあるかもしれませんが、それらはより複雑になる可能性があります。

したがって、次のように言えます。

swap(left, (left + right) / 2);
int pivot = a[left];

これは上記と非常に似ていますが (同一ではありません)、処理がはるかに簡単です。

于 2013-02-23T22:16:03.770 に答える
2

明らかに、あなたが受け入れられた答えを得たことは明らかです。ただし、for (または while) ループを 1 つだけ使用して、ネスト ループも使用せずに、パーティション ロジックをより簡単に実装できることを述べておきます。

int partition(final int[] a, final int left, final int right) {
        // set the last element as pivot
        final int pivot = a[right];
        int i = left - 1, j = left;
        for (; j < right; j++) 
            if (a[j] < pivot) {
                i++;
                swap(a, i, j);
            }       
        // swap a[i+1] and pivot
        swap(a, i + 1, right);
        return i + 1;
    }

そしてあなたのquickSortメソッドで：

if (left < index)
  quickSort(a, left, index-1);
if (index < right)
  quickSort(a, index + 1, right);

それが役に立てば幸い

于 2013-02-23T22:07:15.587 に答える
1

メソッドは の代わりにpartition返す必要があると思います。ji

コードのもう 1 つの問題は、停止条件です。

2 つの個別の条件の代わりに、1 つの条件に変更します。

if (left < right)  {

  do partition & recursive calls

}

完全なコード:

public void quickSort(int[] a, int left, int right) {
    if (left < right) {
      int index = partition(a, left, right);
      quickSort(a, left, index);
      quickSort(a, index + 1, right);
    }
}

private int partition (int[] a, int left, int right) {
    int i = left - 1;
    int j = right + 1;
    int pivot = a[(left+right)/2];

    while (i < j) {

        i++;

        while (a[i] < pivot)
            i++;

        j--;

        while (a[j] > pivot)
            j--;

        if (i < j)
            swap (a, i, j);
    }
    return j;
}   

private void swap (int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}
于 2013-02-23T21:36:13.290 に答える