0

整数のクイックソートアルゴリズムを書いていますが、srand関数で奇妙なセグメンテーション違反エラーが発生します。これがsort.hのコードです。

int distributePivot (int *a, int left, int pivot, int right) {
    int i, j;
    if (pivot != right)
        swapInt(&pivot, &right);
    i = left;
    j = right - 1;
    while (i < j) {
        while (i < j && a[i] <= a[right])
            i++;
        while (j > i && a[j] >= a[right])
            j--;
        if (i < j)
            swapInt(&a[i], &a[j]);
    }
    if (i < right)
        swapInt(&a[i], &a[right]);
    return i;
}

void intArrayQuickSort (int *a, int left, int right) {
    int pivot;
    if (left < right) {
            pivot = rand() % (right - left +1) + left;
        pivot = distributePivot(a, left, pivot, right);
        intArrayQuickSort (a, left, pivot -1);
        intArrayQuickSort (a, pivot, right);
    }
}

そして、これがsort-test.cからの呼び出しです。

    srand(time(NULL));
    intArrayQuickSort(temp, 0, n - 1);

temp整数へのポインタはどこにありますか。

そして、gdbで実行したときに発生するエラーは次のとおりです。

    Program received signal SIGSEGV, Segmentation fault.
    0x00007ffff77e9884 in rand () from /lib64/libc.so.6

手伝ってくれませんか？

どうもありがとうございます。

編集：これはswapInt関数です：

void swapInt (int *a, int *b) {
    int aux = *a;
    *a = *b;
    *b = aux;
}
4

4 に答える 4

1

プログラムロジックにエラーがあります。
たとえば
、メイン
配列= [1,2]
call intArrayQuickSort（array、0、1）; // a：array、left：0、right：1
in intArrayQuickSortivot
= 1 //rand() % (right - left +1) + left;
呼び出しdistributePivot（a、0、 1、1）
distributePivot
でスワップしない（ピボット、右）ピボット== righit
i =0//左
j=0//右-1
ブロック中に実行しないi==j
がスワップを実行する（a [i]、a [right]）because i <right // 0 <1
// a = [2、1] // !! NG
return 0 // intArrayQuickSortピボット=0の
すでに不正な状態 ;//戻り値から：0 call intArrayQuickSort（ a、0、-1）; //左：0、ピボット-1：-1



オペレーションリターンなし
呼び出しintArrayQuickSort（a、1、1）;//ピボット+1：1、右：1
メイン
結果にオペレーションリターンなし：a = [2、1] // NG！

于 2012-06-09T17:50:16.463 に答える
0

の修正版だと思います 

int distributePivot (int *a, int left, int pivot, int right) {
    int i, j;
    if (pivot != right)
        swapInt(&a[pivot], &a[right]);
    i = left;
    j = right - 1;
    while (1) {
        while (i < right && a[i] < a[right])
            i++;
        while (left <= j && a[j] >= a[right])
            j--;
        if (i < j)
            swapInt(&a[i], &a[j]);
        else
            break;
    }
    if(i < right)
        swapInt(&a[i], &a[right]);
    return i;
}
void intArrayQuickSort (int *a, int left, int right) {
    int pivot;
    if (left < right) {
        pivot = rand() % (right - left +1) + left ;
        pivot = distributePivot(a, left, pivot, right);
        intArrayQuickSort (a, left, pivot - 1);
        intArrayQuickSort (a, pivot + 1, right);
    }
}
于 2012-06-10T07:37:05.467 に答える
0

実際に解決策を見つけましたが、なぜそれが機能するのかわかりません。2番目の再帰呼び出しは次のようになります。

intArrayQuickSort (a, pivot + 1, right);

アルゴリズムには意味がありますが、エラーがrand（）にある理由がわかりません。説明はありますか？

于 2012-06-09T14:07:10.273 に答える
-1 
pivot = rand() % (right - left +1) + left;

する必要があります：

pivot = left + rand() % (right - left +1);

または多分：

pivot = left +1 + rand() % (right - left);
于 2012-06-09T13:13:22.330 に答える