[Algorithm] 합병정렬 Merge Sort

🌟 합병정렬 Merge Sort

정의:

• 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법

• 하나의 리스트를 반으로 분할하고 분할된 부분을 정렬하고 다시 합하여 전체를 정렬

원리:

1. 분할: 입력을 같은 크기의 2개의 부분 배열로 분할; 충분히 작은 크기로

2. 정복: 부분 배열을 정렬

3. 결합: 정렬된 부분 배열을 하나의 배열로 통합

구현:

#include <stdio.h>
int sorted[100], count;
void merge(int list[], int left, int mid, int right){
	int i, j, k, l;
    i = left;
    j = mid + 1;
    k = left;
    while(i<=mid && j<=right){	// 한 개의 원소만 남을 때까지
    	if(list[i] <= list[j]){	//바교하여 작은 것을 k++에 추가
        	sorted[k++] = list[i++];
        }
        else{
        	sorted[k++] = list[j++];
        }
    }
    if(i > mid){	// 왼쪽 배열이 남았을 경우
    	for(l=j; l<=right; l++){
        	sorted[k++] = list[l];
        }
    }
    else{	// 오른쪽 배열이 남았을 경우
    	for(l=i; l<=mid; l++){
        	sorted[k++] = list[l];
        }
    }
    for(l=left; l<=right; l++){
    	list[l] = sorted[l];
    }
}

void mergesort(int list[], int left, int right){
	int mid;
	if(left < right){	// 원소가 하나 남을 때까지
		mid = (left+right) / 2;
    	mergesort(list, left, mid);
    	mergesort(list, mid+1, right);
    	merge(list, left, mid, right);
	}
    count++;
}

int main(){
	int list[8] = [11, 22, 33, 44, 55, 66, 77, 88];
    mergesort(list, 0, 7);
    printf("%d\n", count);
    for(int i=0; i<8; i++){
    	printf("%d ", list[i]);
    }
    return 0;
}

당신의 시간이 헛되지 않는 글이 되겠습니다.
I'll write something that won't waste your time.