merge sort (합병 정렬)

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

 

실행

위의 코드를 실행한 결과입니다.

이렇게 실행됩니다.

[프로그래밍/알고리즘] - 정렬 알고리즘 - 삽입 정렬 [Insertion sort]

[프로그래밍/알고리즘] - C자료구조 선택정렬 알고리즘(Selection Sort)

[프로그래밍/알고리즘] - 정렬 알고리즘 - 퀵 정렬 [Quick Sort]