0

Cでマージソート再帰関数を設定しようとして、次のことを思いつきました。

奇妙な動作は、配列のサイズが小さい場合 (約 10)、完全に正常に動作することです。サイズが 10 から 15 の場合、正しくソートされないことがあります (1 つまたは 2 つの値が最終的な配列にランダムに配置されます)。15 より大きい値の場合、常に 1 つまたは 2 つの値が正しくソートされず、1 つまたは 2 つの整数値が非常に大きな負の整数。

たとえば、この配列:[3] [9] [2] [11] [8] [7] [5] [2]

そのようにソートされます：[2] [2] [3] [-254587859] [7] [8] [11]

--

これが私が思いついたコードです:

主要（） ：

int main(int ac, char **av)
{
    int size = atoi(av[1]);
    int *array = malloc(size*sizeof(int));
    int i;

    for (i = 0; i < size; i++) { array[i] = rand() % size; }

    merge_sort(array, 0, size-1);

    print_array(array, size);

    free(array);

    return 0;

}

merge_sort() :

void merge_sort(int array[], int beg, int end)
{
    int mid = (end + beg) / 2;

    if (beg < end)
    {
        merge_sort(array, beg, mid);
        merge_sort(array, mid+1, end);
        merge(array, beg, mid, end);
    }

    return;
}

マージ（）：

void merge(int array[], int beg, int mid, int end)
{
    int size_left = mid - beg + 1;
    int size_right = end - mid;
    int *left = malloc((size_left)*sizeof(int));
    int *right = malloc((size_right)*sizeof(int));
    int i,j,k;

    for (i = 0; i < size_left; i++) { left[i] = array[beg+i]; }
    for (j = 0; j < size_right; j++) { right[j] = array[mid+1+j]; }

    i = 0; j = 0; for (k = beg; k <= end; k++) { array[k] = (left[i] <= right[j]) ? left[i++] : right[j++]; }

    free(left); free(right);

    return;
}

私はそれがメモリ割り当ての問題だと思います.大量のメモリを割り当てることができました（試してみましたが、うまくいきました）が、それは重要ではありません. そこで何が起こっているか分かりますか？

構成: gcc 4.6.2、Windows 7 64 ビット。

4

3 に答える 3

3

My guess is that the problem is line:

for (int k = beg; k <= end; k++) {
    array[k] = (left[i] <= right[j]) ? left[i++] : right[j++];
}

Consider left = [1, 2, 3, 4] and right = [5, 6, 7, 8]. The left will be taken until i = 4 then you try to reference left[4] which is beyond the array and have undetermined value (in Java or other safe languages you would get IndexOutOfBoundException or similar error - in C you are on your own and you have just read some random memory).

You need to ensure that i and j are within array bounds. For example:

 for (int k = beg; k <= end; k++) {
    if (i == size_left) {
        array[k] = right[j++];
    } else if (j == size_right) {
        array[k] = left[i++];
    } else {
        array[k] = (left[i] <= right[j]) ? left[i++] : right[j++];
    }
}

Unfortunately such errors are quite common in C. There are tools, both free and commercial, that allows you to find them. For Linux the Valgrind is usually used. CLang or gcc 4.8.0+ AddressSanitizer would also help with this problem - unfortunately I don't know any free tools for Windows other then it.

于 2013-06-10T21:55:17.943 に答える
3

問題はあなたのマージです：

array[k] = (left[i] <= right[j]) ? left[i++] : right[j++];

iこれは、またはj配列の終わりを過ぎている可能性があるという事実を考慮していません。実際に確認する必要があります：

i = j = 0;
k = beg;

// Merge both
while( i < size_left && j < size_right ) {
    array[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
}

// Merge leftovers
while( i < size_left ) array[k++] = left[i++];
while( j < size_right ) array[k++] = left[j++];
于 2013-06-10T21:55:23.027 に答える
0

わかりました、Maciej と Paddy に感謝します。「マージ」ステップについての私の推論に大きな失敗を指摘してくれました。まさにそれが C の興味深いところです。つまり、「独力で」行動し、間違った行動をとった場合にそれを止めるガイドラインがここにないという感覚です。

あなたの改善に基づいて、ここに私が終わったものがあります：

for (k = beg; k <= end; k++) {
    array[k] = (left[i] <= right[j]) ?
        (i == size_left) ? right[j++] : left[i++] :
        (j == size_right) ? left[i++] : right[j++];
}
于 2013-06-11T09:48:19.543 に答える