C言語関係掲示板過去ログ８１８

C言語関係掲示板

過去ログ

No８１８　マージソート

[戻る]　[ホームページ]

No.10345		ソートに関してです。投稿者---キュール(2003/11/07 03:12:57)
		前にあったクイックソートを元にマージソートを作りましたが、実行してみると順番どおりにならびません。その前にマージソートはこんなプログラムでよいのでしょうか？ #include<stdio.h> #include<stdlib.h> #include<time.h> void mergesort(int A[],int L,int R){ int c=(L+R)/2,k,B[R+1],j=c+1,i; if(L<R){ mergesort(A,L,c); mergesort(A,c+1,R); for(i=L;i<=j-1;i++){ B[i]=A[i]; } for(i=j;i<=R;i++){ B[i]=A[i]; } for(i=L,k=L;k<=R;k++){ if(A[i]<=A[j]){ A[k]=B[i]; i++; } else{ A[k]=B[j]; j++; } } } } int main(void){ int n=8,A[8],i; srand((unsigned int) time(NULL)); for(i=0;i<n;i++){ A[i]=rand()%100; printf("A[%d]=%d\n",i,A[i]); } mergesort(A,0,n-1); putchar('\n'); for(i=0;i<n;i++){ printf("A[%d]=%d\n",i,A[i]); } return 0; }

No.10351		Re:ソートに関してです。投稿者---たか(2003/11/07 13:06:44)
		>前にあったクイックソートを元にマージソートを作りましたが、実行してみると順番どおりにならびません。その前にマージソートはこんなプログラムでよいのでしょうか？惜しいけどちょっと違います。まず配列B[]は関数mergesort()の中で仮引数Rを使って定義できません。ここではスタック領域の浪費を防ぐためstatic配列として定義しています。次に配列B[]へのコピーの仕方が違います。配列でマージソートを書くのは難しいと言われます。リストの方がずっと簡単です。 B[]からA[]へのコピーの仕方は合っています。 #include<stdio.h> #include<stdlib.h> #include<time.h> int B[100]; /* 補助配列 */ void mergesort(int A[], int L, int R) { int c = (L + R) / 2, k, j, i; if (L < R) { mergesort(A, L, c); mergesort(A, c + 1, R); for (i = c + 1; i > L; i--) B[i - 1] = A[i - 1]; for (j = c; j < R; j++) B[R + c - j] = A[j + 1]; for(k = L; k <= R; k++) if (B[i] <= B[j]) A[k] = B[i++]; else A[k] = B[j--]; } } int main(void){ int n=8,A[8],i; srand((unsigned int) time(NULL)); for(i=0;i<n;i++){ A[i]=rand()%100; printf("A[%d]=%d\n",i,A[i]); } mergesort(A,0,n-1); putchar('\n'); for(i=0;i<n;i++){ printf("A[%d]=%d\n",i,A[i]); } return 0; }