c 언어 합병 정렬 알고리즘!

합병 정렬(Merge Sort)

합병 정렬 알고리즘 2개의 정렬된 데이터 집합을 하나의 정렬된 데이터 집합으로 합병

하는 알고리즘 입니다.

c언어로 구현해 봤는데 이해가 안되시는 분은 질문해주시면 알려드리겠습니다.

-정렬된 두 데이터 집합을 하나의 정렬된 데이터집합으로 합병

-a1, a2, a의 현재 위치를 나타내는 인덱스를 i, j, k라 할 때(초기값 i=j=k=0)

a1[i] < a2[j] 이면 a[k] = a1[i], i++, k++

a1[i] > a2[j] 이면 a[k] = a2[j], j++, k++

어느 한 list를 다 처리하면 나머지 리스트의 데이터를 복사한다.

a1의 데이터의 수 n1, a2의 데이터의 수를 n2라고 할 때

while (j < n2) a[k]=a2[j], k++, j++

while (I < n1) a[k]=a1[i], k++, i++

합병 정렬 프로그래밍

#include<stdio.h>

int merge(int *a1,int *a2,int *a,int n1, int n2)

{

int i=0,j=0,k=0;

while(i<n1&&j<n2)

{

if(a1[i]<a2[j])//a1이더 작으면 a1를 a 배열에 넣고 인덱스 값을 1씩증가시킨다.

{

a[k++]=a1[i++];

}

else if(a1[i]>a2[j])//a2가 더 작으면 a2를 a 배열에 넣고 인덱스값을 1씩증가 시킨다.

{

a[k++]=a2[j++];

}

else

{

a[k++]=a1[i++];

j++;

}

}

if(i==n1)

while(j<n2)a[k++]=a2[j++];

else

while(i<n1) a[k++] = a[i++];

return k;

}

int print_list(int *list,int n)//합병 정렬 출력하기

{

int i;

for(i=0;i<n;i++)

{

printf("%4d",list[i]);

}

printf("\n\n");

}

void main()

{

int list1[]={10,20,30,40,50};//정렬된 데이터 집합1

int list2[]={15,17,33,35,37};//정렬된 데이터 집합 2

int list[100];//1,2,를 정렬해서 하나의 정렬된 데이터 집합을 만들 배열

int n1,n2,n;

n1=sizeof(list1)/sizeof(int);

n2=sizeof(list2)/sizeof(int);

n=merge(list1,list2,list,n1,n2);

printf("합병된데이터리스트:\n");

print_list(list,n);

}