merge sort (합병 정렬)
- 프로그래밍/알고리즘
- 2020. 4. 28.
250x250
merge sort(합병 정렬)
안녕하세요.
이번에는 merge sort코드입니다.
분할 정복 알고리즘의 하나입니다.
간단하게 설명하면 분할하고 정렬하고 결합하여 결국 전체가 정렬되게 하는 알고리즘입니다.
흠... 설명이 좀..ㅋㅋㅋㅋ
- merge sort[합병 정렬]코드.
- 코드 실행 결과.
merge sort 코드
코드는 아래와 같습니다.
과정을 확인하기 위해 조금 쓸데없는 코드도 넣었습니다.
#include<stdio.h>
void partition(int list[],int left,int right);//sort할 배열을 나눠주는 함수.
void mergesort(int list[],int p,int r,int q);//sort
void view(int list[],int l,int m, int r);//중간 상황을 보기 위한 함수.
int sorted[9];
int main(){
int list[9]={9,6,7,8,5,4,3,2,1};//sort할 배열.
int i;
/*정렬 전.*/
printf("정렬 전= ");
for(i=0;i<9;i++){
printf("%d ",list[i]);
}
printf("\n");
/*정렬*/
partition(list,0,8);
/*정렬 후*/
printf("정렬 후= ");
for(i=0;i<9;i++){
printf("%d ",list[i]);
}
return 0;
}
void partition(int list[],int left,int right){//배열,처음,끝
int middle;
if(left<right){
middle=(left+right)/2;
view(list,left,middle,right);//순서를 보여줌.
//printf("\nleft=%d, middle=%d, right=%d \n",left,middle,right);
partition(list,left,middle);//앞쪽.
partition(list,middle+1,right);//뒤쪽.
mergesort(list,left,middle,right);
}
}
void mergesort(int list[], int left, int mid, int right) {
int i=left, middle=mid+1, t=left, a;
int tmp[100]; //임시 배열
while(i<=mid && middle<=right) {
if(list[i] <= list[middle]) {
tmp[t++] = list[i++];
}
else tmp[t++] = list[middle++];
}
while(i<=mid) {//왼쪽배열이 남은 경우
tmp[t++] = list[i++];
}
while(middle<=right) {//오른쪽 배열이 남은 경우
tmp[t++] = list[middle++];
}
for(a=left; a<=right; a++) {
list[a] = tmp[a];
}
for(a=0;a<9;a++)//
printf("%d ",list[a]);
printf("\n");
}
void view(int list[],int l,int m, int r){
int i;
printf("왼= ");
for(i=l;i<=m;i++)
printf("%d ",list[i]);
printf("\n");
printf("오= ");
for(i=m+1;i<=r;i++)
printf("%d ",list[i]);
printf("\n");
}
실행
위의 코드를 실행한 결과입니다.
이렇게 실행됩니다.