자료구조(정렬 알고리즘) - 합병, 병합 정렬(Merge Sort)

안녕하세요, 츄르 사려고 코딩하는 집사 코집사입니다.

이번 글에서는 Merge Sort의 C언어 소스 코드를 올리려고 합니다.

Merge Sort의 C언어 소스코드

#include<stdio.h>

int A[10000];

int B[10000]; // 빈 배열

int MergeSort(int A[], int left, int right); 

int Merge(int A[], int left, int mid, int right);

int main()

{

   int number;

   printf("배열 크기 입력 : ");

   scanf("%d",&number);

   for(int i=0;i<number;i++)

   {

      printf("%d번째 배열 값 입력 :",i);

      scanf("%d",&A[i]);

   }

   MergeSort(A,0,number-1);

   for(int a=0;a<number;a++)

   {

    printf("%d",A[a]);

   }

}

int MergeSort(int A[], int left, int right)

{

   int mid;

   if(left<right)

   {

       mid  = (left + right) / 2;

   MergeSort(A, left, mid);

   MergeSort(A, mid+1, right);

   Merge(A, left, mid, right);

}

}

int Merge(int A[], int left, int mid, int right)

{

int i,j,k,l;

i = left;

j = mid + 1;

k = left;

while(i <= mid && j <= right)

{

if(A[i]<=A[j])

{

B[k++] = A[i++];

}

else

{

B[k++] = A[j++];

}

}

if(i>mid)

{

for(l=j;l<=right;l++)

{

B[k++] = A[l];

}

}

else

{

for(l=i;l<=mid;l++)

{

B[k++] = A[l];

}

}

for(l=left;l<=right;l++)

{

A[l] = B[l];

}

}