[자료구조 복습 9] Merge sort 합병정렬

머지소트 

 

머지소트의 원리는 '분할정복'이다. 

이미지 출처- geeks for geeks 

1) 배열을 더이상 쪼갤 수 없을 때까지 쪼갠다

2) 쪼개진 배열을 병합, 정렬한다. 가장처음엔 1개로 이루어진 배열 두개를 정렬하여 길이가 2인 배열을만들고,

이를 또 길이가 2인 배열 두개를 병합/정렬하여 길이가 4인 배열을 만든다..-> 배열이 모두 병합/정렬될 때까지 한다.

 

 

머지소트는 재귀의 깊이가 O(log2N)이고, 각 재귀 당 비교 및 스왑연산이 평균적으로 n번수행된다고 보면,

시간복잡도는 O(Nlog2N) 이 되겠다.

머지소트의 최대 단점이라하면, in place 알고리즘이 아니라는 것이다. 즉, 머지소트는 외부의 다른 배열을 만들고, 그 배열에서 정렬한 후, 정렬된 값을 다시 원래의 배열로 옮겨줘야한다.

 

 

 

<자바소스>

public class Sort {
	static int[] sorted= new int[8]; //정렬 후 임시 배열 
	public static void main(String[] args) {
		int[] arr= new int[3];
		for(int i =0 ; i<3; i++) {
			arr[i]=(int)(Math.random()*50)+1;
		}
		mergeSort(arr,0,arr.length-1);
		for(int i = 0; i<3; i++) {
			System.out.println(arr[i]); 	}
	}
	
	public static void merge(int arr[], int front, int mid, int rear) {
		int i= front;
		int j= mid+1;
		int k = front;
		
		while(i<=mid && j<=rear) {
			if(arr[i]<arr[j]) { //arr[i]가 더 작은경우 
				sorted[k]=arr[i];
				i++;
			}
			else { //arr[j]가 더 작거나 같은 경우 
				sorted[k]=arr[j]; 
				j++;
			}
			k++;
		}
		
        //남은요소들 밀어넣기 
		while(i<=mid) {
			sorted[k]=arr[i];
			i++;k++;
		}
		while(j<=rear) {
			sorted[k]=arr[j];
			j++;k++;
		}
		//정렬 후 다시 arr 배열로 옮기기 
		for(int n= front; n<=rear; n++) {
			arr[n]=sorted[n];
		}
	}
	public static void mergeSort(int arr[], int front, int rear) {
		int mid;
		if(front<rear) { //배열의 길이가 2이상 일 경우에만 
			mid=(front+rear)/2;
			mergeSort(arr,front,mid); //분할 정렬
			mergeSort(arr,mid+1,rear); //분할 정렬 
			merge(arr,front,mid,rear); //합병 
		}
	}
}

 

<C ++ 소스>

#include <iostream>
using namespace std;
#define MAX_ARR 20
int tmpArr[MAX_ARR] = { 0, };

void merge(int arr[], int first, int mid, int last) {
	int pre = first;
	int post = mid+1; 
	int k = first;
	cout << first << last << endl;
	//각각 더 작은값들로 비교하여 tmpArr에 순서대로 넣어주기.
	while (pre !=mid+1 || post !=last+1) {
		
		if (arr[pre] <= arr[post]) {
			tmpArr[k++] = arr[pre++];
		}
		else {
			tmpArr[k++] = arr[post++];
		}
	}
	//남은 값들 넣어주기
	while (pre != mid+1) { tmpArr[k++] = arr[pre++];}
	while (post != last + 1) { tmpArr[k++] = arr[post++];}

	
	for (int j = first; j <= last; j++) {
		arr[j] = tmpArr[j];
	}
}

void merge_sort(int arr[], int first, int last) 
{
	int mid;
	if (first < last) {
		mid = (first + last) / 2;
		merge_sort(arr, first, mid); //분할
		merge_sort(arr, mid + 1, last);
		
		merge(arr, first, mid, last); //합병
	}
}