0

私は宿題の一部としてクイックセレクトアルゴリズムを実装しようとしています。クイックソートがどのように機能するかを読んで、パーティションがどのように機能するかを知り、5つの要素の中央値などを見つけました。しかし、パーティション化に関しては、私はスープにいます。

(less than pivot) | pivot | (greater than pivot)パーティションの結果にフォームの要素が含まれていないことに気付きました。私はこれに頭を悩ませてきましたが、コツをつかむことができないようです。

ウィキペディアから採用したクイックセレクトアルゴリズムで、反復バージョンを使用しています（私が言及した要件）。私のクイックセレクトアルゴリズムは次のとおりです。

public static Numbers quickselect(Numbers[] list, int arraylength,
        int kvalue) {

    int start = 0, end = arraylength - 1;
    if (arraylength == 1)
        return list[start];
    while (true) {

        int newPivotIndex = partition(list, start, end);
        int pivotDist = newPivotIndex - start + 1;
        if (pivotDist == kvalue)
            return list[newPivotIndex];
        else if (kvalue < pivotDist)
            end = newPivotIndex - 1;
        else {
            kvalue = kvalue - pivotDist;
            start = newPivotIndex - 1;
        }
    }

私のパーティションアルゴリズム：

    private static int partition(Numbers[] list, int start, int end) {
        Numbers[] tempMedianArray = new Numbers[5];
        tempMedianArray[0] = list[start];
        tempMedianArray[1] = list[(start + end) / 4];
        tempMedianArray[2] = list[(start + end) / 12];
        tempMedianArray[3] = list[(start + end) / 2];
        tempMedianArray[4] = list[end];
        Numbers pivot = getmedian(tempMedianArray);
           int i = start, j = end;

          while (i <= j) {
                while (compare(list[i], pivot).equals(Order.LESSER)){
                      i++;
                }
                while (compare(list[j], pivot).equals(Order.GREATER)){
                    j--;
                      }
                if (i <= j) {
                    Numbers tmp = list[i];
                      list[i] = list[j];
                      list[j] = tmp;
                }
          };

ピボットが選択されると、標準のHoareのアルゴリズムが機能すると思いました。しかし、私がドライラン自体を実行するとき、私は自分が間違っていることを知っています。

中央値5ピボットで機能するパーティションアルゴリズムの適切な実装を手伝ってくれる人はいますか？

4

2 に答える 2

0

どうですか：

tempMedianArray[0] = list[start];
tempMedianArray[1] = list[(start + end) / 4];
tempMedianArray[3] = list[(start + end) / 2];
tempMedianArray[2] = list[3 * (start + end) / 4];
tempMedianArray[4] = list[end];
于 2012-08-24T23:13:43.060 に答える
0

一時配列インデックスを取得している間、開始を追加し続ける必要があります。

            int localStart = 0;
    int localEnd = end - start;
    Number[] local = new Number[5];
    tempMedianArray[0] = list[localStart + start];
    tempMedianArray[1] = list[(localStart + localEnd) / 4 + start];
    tempMedianArray[2] = list[(localStart + localEnd) / 4 * 3 + start];
    tempMedianArray[3] = list[(localStart + localEnd) / 2 + start];
    tempMedianArray[4] = list[localEnd + start];
于 2012-08-26T05:31:04.633 に答える