ノーヒントで0から一気に書き上げたオリジナルのマージソートプログラム。ポインタをふんだんに使用したため、普通のソースとは一味ちがう。
#include <stdio.h> #include <stdlib.h> void devide(int end,int *data); void merge1(int *leftarray,int *rightarray,int n,int *data); void merge2(int *leftarray,int *rightarray,int n,int *data); void showdata(int *array,int n); int main(void) { int i,*base,N; scanf("%d ",&N); base=(int *)malloc(N*sizeof(int)); if(!base){ printf("メモリの割り当てに失敗しました。¥n"); exit(1); } for(i=0;i<N;i++) scanf("%d ",&base[i]); showdata(base,N); devide(N-1,base); showdata(base,N); return 0; } void devide(int end,int *data) { int middle,*leftarray,*rightarray,i; if(!end) return; middle=end/2; if(end%2){ leftarray=(int *)malloc((middle+1)*sizeof(int)); if(!leftarray){ printf("メモリの割り当てに失敗しました。¥n"); exit(1); } rightarray=(int *)malloc((middle+1)*sizeof(int)); if(!rightarray){ printf("メモリの割り当てに失敗しました。¥n"); exit(1); } for(i=0;i<middle+1;i++){ leftarray[i]=data[i]; rightarray[i]=data[middle+1+i]; } devide(middle,leftarray); devide(middle,rightarray); merge1(leftarray,rightarray,middle+1,data); } else{ leftarray=(int *)malloc((middle+1)*sizeof(int)); if(!leftarray){ printf("メモリの割り当てに失敗しました。¥n"); exit(1); } rightarray=(int *)malloc(middle*sizeof(int)); if(!rightarray){ printf("メモリの割り当てに失敗しました。¥n"); exit(1); } for(i=0;i<middle;i++){ leftarray[i]=data[i]; rightarray[i]=data[middle+1+i]; } leftarray[middle]=data[middle]; devide(middle,leftarray); devide(middle-1,rightarray); merge2(leftarray,rightarray,middle,data); } free(leftarray); free(rightarray); } void merge1(int *leftarray,int *rightarray,int n,int *data) { int leftcount=0,rightcount=0; do{ if(leftarray[leftcount]<=rightarray[rightcount]){ data[leftcount+rightcount]=leftarray[leftcount]; leftcount++; } else{ data[leftcount+rightcount]=rightarray[rightcount]; rightcount++; } }while(leftcount<n && rightcount<n); while(leftcount<n){ data[n+leftcount]=leftarray[leftcount]; leftcount++; } while(rightcount<n){ data[n+rightcount]=rightarray[rightcount]; rightcount++; } } void merge2(int *leftarray,int *rightarray,int n,int *data) { int leftcount=0,rightcount=0; do{ if(leftarray[leftcount]<=rightarray[rightcount]){ data[leftcount+rightcount]=leftarray[leftcount]; leftcount++; } else{ data[leftcount+rightcount]=rightarray[rightcount]; rightcount++; } }while(leftcount<n+1 && rightcount<n); while(leftcount<n+1){ data[n+leftcount]=leftarray[leftcount]; leftcount++; } while(rightcount<n){ data[n+1+rightcount]=rightarray[rightcount]; rightcount++; } } void showdata(int *array,int n) { int i; for(i=0;i<n;i++) printf("%d ",array[i]); printf("¥n"); }
※コメント投稿者のブログIDはブログ作成者のみに通知されます