0

クイックソートアルゴリズムを変更し、乱数であるピボットを実装して、O（n ^ 2）の問題を回避しようとしています。乱数を使用したいのですが、コードでセグメンテーション違反が発生します。

int random (int num) {
    int random = rand() % (num - 1);
    return random;
}

int* partition (int* first, int* last);
void quickSort(int* first, int* last) {
    if (last - first <= 1) return;

    int* pivot = partition(first, last);
    quickSort(first, pivot);
    quickSort(pivot + 1, last);
}

int* partition (int* first, int* last) {   
    int* pos = (first + random(last - first));
    int pivot = *pos;
    int* i = first;
    int* j = last - 1;

    for (;;) {
        while (*i < pivot && i < last) i++;
        while (*j >= pivot && j > first) j--;
        if (i >= j) break;
        swap (*i, *j);
    }
    swap (pos, i);
    return i;
}
4

1 に答える 1

5

関数は、範囲内ではなく、範囲外random()の値を生成します。

int random (int num) {
    int random = rand();
    while (random > 1 && random < num - 1) {
        random = rand();
    }
    return random;
}

これによりpartition()、範囲外の要素を逆参照しようとしたときにセグメンテーション違反が発生します。

私のアドバイスは、書き直しrandom()て、ループを完全に回避することです（範囲が狭い場合、ループは非常に高価になる可能性があります）。

于 2012-05-23T07:25:41.537 に答える