自画自賛

ノーヒントで０から一気に書き上げたオリジナルのマージソートプログラム。ポインタをふんだんに使用したため、普通のソースとは一味ちがう。

#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");
}