2

ユーザー入力から10個の整数を配列に取り、再帰マージソートを使用してソートする宿題のコードをCで記述しようとしています。ポインターについてはまだ調べていないので、コードでそれを使用することは避けたいと思いました (多くのオンラインの例ではポインターを使用しています)。

これが私のコードです：

/* This code will take input for 10 integers given by the user
into an array, sort them with a recursive merge function
and print the updated array in ascending order. */

#include <stdio.h>
#define ARRSIZE 10

void merge_sort (int arr[], int temp[], int left, int right);
void merge (int arr[], int temp[], int left, int mid, int right);

int main (void){
    int arr[ARRSIZE], temp[ARRSIZE], left, right, i;

    printf("Enter 10 integers for an array:");
    for(i=0;i<ARRSIZE;i++){
        printf("\narray value %d:", i+1);
        scanf("%d", &arr[i]);
    }
    left = 0;
    right = ARRSIZE-1;

    merge_sort(arr, temp, left, right);

    printf("\nHere is your updated array:");
    printf("\n{");
    for(i=0;i<ARRSIZE;i++){
        printf("%d,", arr[i]);
    }
    printf("}");

    return 0;
}

void merge_sort (int arr[], int temp[], int left, int right){
    if(left<right){
        int mid = (right-left)/2;
        merge_sort(arr, temp, left, mid);
        merge_sort(arr, temp, mid+1, right);
        merge(arr, temp, left, mid, right);
    }
}

void merge (int arr[], int temp[], int left, int mid, int right){
    int i, j, tempi = 0;
    for(i=left, j=mid+1; i<=mid && j<=right ;){
        // mid+1 is the start of the right array
        if(arr[i]<arr[j] && i<=mid){
            temp[tempi] = arr[i];
            tempi++;
            i++;
        }
        else if(arr[i]>arr[j] && j<=right){
                temp[tempi] = arr[j];
                tempi++;
                j++;
             }
    }
    for(i=0,j=right; i<=j; i++){
        arr[i] = temp[i];
    }
}

これを Linux シェルで実行すると、セグメンテーション違反が発生し続けます。助言がありますか？

4

1 に答える 1

2

さて、私はすでに 1 つの微妙なバグを発見しましたint mid = (right-left)/2;:int mid = (left+right)/2;

また、私が見つけたフローは次のとおりです。

  1. tempi = left簡単にするために使用する必要があります。配列の受信部分を一時配列の対応する部分にコピーするだけです。

  2. マージ サイクルでは、インクリメントするテンポをfor定義内に配置できます。

    for( ...; ...; ++テンポ)

  3. そのループ内では、その場所から値を読み取った後に境界を確認します。これは非常に悪いです。とても。ただし、定義内の境界をチェックしているという理由だけで、ここで問題に遭遇することはありませんfor:)単純にそれらを削除します:

    for (i = left, j = 1 + mid; i <= mid && j <= right; ++tempi)
{  
    if (arr[i] < arr[j])        temp[tempi] = arr[i++];
    else /* arr[j] <= arr[i] */ temp[tempi] = arr[j++];
}

  4. いずれかのサブ配列が最後に達したときにこのループが終了するため、残りの項目を別のサブ配列から temp[] にコピーする必要があります。

    if (i > mid) i = j; /* if we need to copy right subarray */
for (; tempi <= right; ++tempi, ++i) temp[tempi] = arr[i];

  5. したがって、一時配列からのコピーバックは次のようになります

     for (i = left; i <= right; ++i) arr[i] = temp[i];
于 2013-02-18T01:29:17.323 に答える