0

マージ関数でループをmergesort使用するためのコードを C で記述しようとしています。for残念ながら、それは機能していません。関数では、 on 10を降順でmain作成し、関数を呼び出してそれらを並べ替えます。昇順が実現されず、いくつかの配列サイズではいくつかの長い数値が侵入するため、マージ関数には明らかにエラーがあります。私は何を間違っていますか？関数は次のとおりです。arrayintsmergesort

#include <stdio.h>
#include <stdlib.h>


void mergesort(int array[], int left, int right);

int main()
{
    int i;
    int arr[10];
    for(i=10;i>0;i--){
        arr[10-i]=i;
    }
    for(i=0;i<10;i++){
        printf("arr[%d] = %d\n",i,arr[i]);
        }
    mergesort(arr,0,9);
    puts("\n");
    for(i=0;i<10;i++){
        printf("arr[%d] = %d\n",i,arr[i]);
        }
    return 0;
}

void mergesort(int array[], int left, int right)
{
    void merge(int array[],int left, int mid, int right);
    int mid;
    if(left<right){
        mid=(left+right)/2;
        mergesort(array,left,mid);
        mergesort(array,mid+1,right);
        merge(array,left,mid,right);
    }
}

void merge(int array[], int left, int mid, int right)
{
    int i;
    int l=0;
    int r=mid+1;
    int arr_sorted[10];

    for(i=0;i<=right;i++){
        if((l<=mid) && (r<=right)){
            if(array[l]<array[r]){
                arr_sorted[i]=array[l];
                l++;
            }
            else {
                arr_sorted[i]=array[r];
                r++;
            }
        }
        if(l>mid){
            arr_sorted[i]=array[r];
            r++;
        }
        if(r>right){
            arr_sorted[i]=array[l];
            l++;
        }
    }
    for(i=0;i<=right;i++){
        array[i]=arr_sorted[i];
    }
}
4

3 に答える 3

5

最初に奇妙に見えるのは、leftパラメータをに渡す理由ですが、からをmerge繰り返します。この関数では使用していません。0rightleft

于 2012-12-30T09:36:31.957 に答える
3

マージ機能で必要だったいくつかの修正:

void merge(int array[], int left, int mid, int right)
{
    int i;
    int l=left; //If you are passing left, then it should be used here !!
    int r=mid+1;
    int arr_sorted[10];

    for(i=0;(l<=mid)&&(r<=right);i++){ 
//Your condition for this loop unnecessarily complicates the rest of the code. This is a better way to go about it
//The loop body is fine
       if(array[l]<array[r]){
                arr_sorted[i]=array[l];
                l++;
            }
            else {
                arr_sorted[i]=array[r];
                r++;
            }
        }

//Now, checking for remaining elements and adding them to the result
//The conditions are simple because of the test condition we used in the previous for loop
        if(l>mid){
           for(;r<=right;r++,i++) arr_sorted[i]=array[r];
        }
        if(r>right){
            for(;l<=mid;l++,i++)  arr_sorted[i]=array[l];
        }
    }
    for(i=0;i<=right;i++){
        array[i]=arr_sorted[i];
    }
}

また、スタイルの問題として、前方宣言を 1 つの場所に保持するようにしてください (関数が関連しているため)。それ以外の ：

void mergesort(int array[], int left, int right)
{
    void merge(int array[],int left, int mid, int right);//This line should be moved to the top with the mergesort forward declaration
    int mid;
    if(left<right){
        mid=(left+right)/2;

やってみてください：

#include <stdio.h>
#include <stdlib.h>


void mergesort(int array[], int left, int right);
void merge(int array[],int left, int mid, int right); // <--------

ただし、これは好みの問題です。

于 2012-12-30T09:43:03.723 に答える
1

これがマージソート全体です。違いがわかります。他にご不明な点がありましたらお知らせください。stdlibにはマージソートが実装されているため、名前を変更する必要がありました。

#include <stdio.h>
#include <stdlib.h>


int mymergesort(int array[], int left, int right);

int main()
{
    int i;
    int arr[10];
    for(i=10;i>0;i--){
        arr[10-i]=i;
    }
    for(i=0;i<10;i++){
        printf("arr[%d] = %d\n",i,arr[i]);
        }

    mymergesort(arr,0,9);
    puts("\n");
    for(i=0;i<10;i++){
        printf("arr[%d] = %d\n",i,arr[i]);
        }
    return 0;
}

int mymergesort(int array[], int left, int right)
{
    void mymerge(int array[],int left, int mid, int right);
    int mid;

    mid=(left+right)/2;
    if(left<right){
        mymergesort(array,left,mid);
        mymergesort(array,mid+1,right);
        mymerge(array,left,mid,right);
    }
    return 0;
}

void mymerge(int array[], int left, int mid, int right)
{
    int i=0;
    int l=left;
    int r=mid+1;
    int arr_sorted[10];

    for(i=left;i<=right;){
        if((l<=mid) && (r<=right)){
            if(array[l]<array[r]){
                arr_sorted[i]=array[l];
                l++;
                i++;

            }
            else {
                arr_sorted[i]=array[r];
                r++;
                i++;
            }
        }

        if(l>mid){
            for(;r<=right;r++){   
                arr_sorted[i]=array[r];
                i++;

            }   
            break;
        }
        if(r>right){
            for(;l<=mid;l++){

                 arr_sorted[i]=array[l];
                    i++; 
            }
            break;
        }
    }
    for(i=left;i<=right;i++){
        array[i]=arr_sorted[i];
    }
}
于 2012-12-30T11:59:59.873 に答える