2

配列に存在するピボット要素に依存しないインプレース パーティショニングアルゴリズム (Quicksort 実装で使用される種類の)はありますか?

つまり、配列要素は次の順序で配置する必要があります。

  • ピボットよりも小さい要素 (存在する場合)
  • ピボットに等しい要素 (存在する場合)
  • ピボットより大きい要素 (存在する場合)

ピボット要素が配列に存在する場合は (並べ替え後に) インデックスを返す必要があり、そうでない場合は特別な値を返す必要があります。これは、順序を維持するために要素を挿入できるインデックスの1 の補数である可能性があります (Java の標準のバイナリ検索関数の戻り値のように)。

私が見た実装では、ピボット要素のインデックスをパラメーターとして指定する必要があります (または常に配列の先頭にある必要があります)。残念ながら、ピボットが配列内に存在するかどうか (または配列のどこにあるか) は事前にわかりません。配列にあります。)

編集（メリットンのコメントへの返信）：次の条件のいずれかが当てはまると想定することもできます。

  • 配列の長さが < 2、または
  • 少なくとも 1 つの要素が <= ピボットで、少なくとも 1 つの要素が >= ピボットです。

配列内に値が重複している可能性があります (ピボット値の重複を含む)。

4

3 に答える 3

1

これは興味深い問題でした。アレイを1回連続して通過することでそれを行うことができます。以下のC＃のコード例。これは、と呼ばれる整数の配列とa値を想定していpivotます。

// Skip initial items that are < pivot
int iInsert = 0;
while (iInsert < a.Length && a[iInsert] < pivot)
{
    ++iInsert;
}
// Skip items that are = pivot
int numPivot = 0;
while (iInsert < a.Length && a[iInsert] == pivot)
{
    ++iInsert;
    ++numPivot;
}

int iCurrent = iInsert;
// Items will be added AFTER iInsert.
// Note that iInsert can be -1.
--iInsert;
while (iCurrent < a.Length)
{
    if (a[iCurrent] < pivot)
    {
        if (numPivot == 0)
        {
            ++iInsert;
            int temp = a[iInsert];
            a[iInsert] = a[iCurrent];
            a[iCurrent] = temp;
        }
        else
        {
            ++iInsert;
            int temp = a[iInsert];
            a[iInsert - numPivot] = a[iCurrent];
            a[iCurrent] = temp;
            a[iInsert] = pivot;
        }
    }
    else if (a[iCurrent] == pivot)
    {
        ++iInsert;
        int temp = a[iInsert];
        a[iInsert] = pivot;
        a[iCurrent] = temp;
        ++numPivot;
    }
    ++iCurrent;
}

int firstPivot = iInsert - numPivot + 1;

おそらくいくつかの最適化の機会があります。

このアプローチの興味深い点は、受信データのストリームから構築するように簡単に適応できることです。いくつのアイテムが来るかを知る必要はありません。動的にサイズ変更できるリストを使用するだけです。最後のアイテムが入ってくると、リストは正しい順序になっています。

于 2011-10-12T23:03:54.227 に答える
0

あなたは運がいいです: 先月のコーディング kata はクイックソートを実装することでした。これが私が思いついたものです：

/**
 * Sorts the elements with indices i such that l <= i < r
 */
private static void qsort(int[] a, int left, int right) {
    int l = left;
    int r = right - 1;

    if (l >= r) {
        return;
    }

    int pivot = a[l];
    l++;
    for (;;) {
        while (l <= r && a[l] <= pivot) l++;
        while (a[r] > pivot  && l < r) r--;

        if (l < r) {
            int t = a[l];
            a[l] = a[r];
            a[r] = t;
        } else {
            break;
        }
    }
    l--;
    a[left] = a[l];
    a[l] = pivot;

    qsort(a, left, l);
    qsort(a, r, right);
}

ご覧のとおり、アルゴリズムはピボットの元の場所を使用して、ピボットの値を見つけ、ピボットをパーティション間のインデックスに交換します。

ピボットが存在することがわからない場合は、単純にピボットと等しい値を値 < ピボットのように扱います。つまり、要素をピボットより小さい、等しい、大きいの 3 つのグループに分割するのではなく、次のように分割します。ピボット以下とピボット以上の 2 つのグループは、これらのパーティションのそれぞれで再帰します。この解決策は正しいでしょう。

ただし、終了は保証されなくなります。QuickSort は終了することが知られています。これは、各再帰ステップがその呼び出し元よりも短い配列スライスで動作し、配列スライスがピボット要素を含まないために短いことが知られているためです。これは、修正されたアルゴリズムには当てはまりません。実際、終了がピボット値の選択戦略に依存することは容易にわかります。

于 2011-10-13T17:45:59.913 に答える
0

もう 1 つの可能性は、メソッドを 2 つに分割することです。1 つは [<= ピボット、> ピボット] に分割し、もう 1 つはその結果の最初の部分を [< ピボット、>= ピボット] に分割します。

public static int partitionLE(double[] a, int left, int right, double pivot) {
    double x, y;
    if (left >= right) return left;
    for (;;) {
        while ((x = a[left]) <= pivot) {
            if (++ left >= right) return left;
        }
        while ((y = a[right-1]) > pivot) {
            if (left >= -- right) return left;
        }
        if (left < right) {
            a[left] = y;
            a[right-1] = x;
        } else {
            return left;
        }
    }
}
public static int partitionLT(double[] a, int left, int right, double pivot) {
    double x, y;
    if (left >= right) return left;
    for (;;) {
        while ((x = a[left]) < pivot) {
            if (++ left >= right) return left;
        }
        while ((y = a[right-1]) >= pivot) {
            if (left >= -- right) return left;
        }
        if (left < right) {
            a[left] = y;
            a[right-1] = x;
        } else {
            return left;
        }
    }
}
public static int partition(double[] a, int left, int right, double pivot) {
    int lastP = partitionLE(a, left, right, pivot);
    int firstP = partitionLT(a, left, lastP, pivot);
    if (firstP < lastP) {
        return firstP;
    } else {
        return ~firstP;
    }
}
于 2011-10-13T20:18:22.037 に答える