0

C++ でバケットソート アルゴリズムを作成しようとしていますが、まったく機能しません。実行するたびに、多数の新しい数値が配列に追加されます。多くの場合、数十億のような非常に大きな数値が配列に追加されます。これがなぜなのか誰か知っていますか？コードは次のとおりです-（サイズ100の配列を0から〜37000の乱数で渡していることに注意してください。挿入ソート機能は完全に機能し、複数回テストされています）

誰かが間違っていることを指摘できれば幸いです。

void bucketSort(int* n, int k) 
{
    int c = int(floor(k/10)), s = *n, l = *n;
    for(int i = 0; i < k; i++) {
        if(s > *(n + i)) s = *(n + i);
        else if(l < *(n + i)) l = *(n + i);
    }
    int bucket[c][k + 1];
    for(int i = 0; i < c; i++) {
        bucket[i][k] = 0;
    }

    for(int i = 0; i < k; i++) {
        for(int j = 0; j < c; j++) {
            if(*(n + i) >= (l - s)*j/c) {
                continue;
            } else {
                bucket[j][bucket[j][k]++] = *(n + i);
                break;
            }
        }
    }

    for(int i = 0; i < c; i++) {
        insertionSort(&bucket[i][0], k);
    }
}
4

1 に答える 1

0

この行はコンパイルされません。int bucket[c][k + 1];

問題はバケット インデックスにあると思います。この部分はこちら

for(int j = 0; j < c; j++) {
   if(*(n + i) >= (l - s)*j/c) {
        continue;
   } else {
        bucket[j][bucket[j][k]++] = *(n + i);
        break;
   }
}

以下と同等のことはしません:

  insert n[i] into bucket[ bucketIndexFor( n[i]) ]

まず、インデックスを 1 つずらします。そのため、最後のバケットの数字の区切りも逃しています。また、インデックスの計算では の[0,l-s]代わりに範囲が使用されるため、小さなエラーが発生します。これは、等しい[s,l]場合にのみ同じです。s0

私が次のように書くときbucketIndex：

int bucketIndex( int n, int c, int s, int l )
{
    for(int j = 1; j <= c; j++) {
        if(n > s + (l-s)*j/c) {
            continue;
        } else {
            return j-1;
        }
    }
    return c-1;
}

アルゴリズムの主要部分を次のように書き直します。

std::vector< std::vector<int> > bucket( c );

for(int i = 0; i < k; i++) {
    bucket[ bucketIndex( n[i], c, s, l ) ].push_back( n[i] );
}

アイテムをバケットに適切に挿入します。

于 2013-02-16T19:54:03.010 に答える