11장 정렬 병합 방식<2-way 병합, n-way 병합>

정렬

순서 없이 배열되어 있는 자료들을 작은 것부터 큰 것 순서의 오름차순이나 큰 것부터 작은 것 순서의 내림차순으로 재배열하는 것이다. 정렬 방법은 수행되는 위치에 따라서 컴퓨터 메모리 내부에서 수행하는 내부 정렬과 메모리의 외부인 보조 기억 장치에서 수행하는 외부 정렬로 분류할 수 있고, 수행 방법에 따라 비교식 정렬과 분산식 정렬로 구분할 수 있다.

 

내부 정렬

1. 교환 방식 - 키를 비교하고 교환하여 정렬하는 방식(선택, 버블, 퀵)

2. 삽입 방식 - 키를 비교하고 삽입하여 정렬하는 방식(삽입, 셸)

3. 병합 방식 - 키를 비교하고 병합하여 정렬하는 방식(2-way 병합, n-way 병합)

4. 분배 방식 - 키를 구성하는 값을 여러 개의 부분집합에 분배하여 정렬하는 방식(기수)

5. 선택 방식 - 이진 트리를 사용하여 정렬하는 방식(힙, 트리)

 

정렬되지 않은 { 69, 10, 30, 2, 16, 8, 31 }을 예시로 들겠다.

n-way 병합

병합 정렬은 정렬되지 않은 자료들을 부분집합으로 분할하고 각 부분집합에 대해서 정렬 작업을 완성한 후에 다시 결합하는 분할 정복 기법을 사용한다. n개의 정렬된 자료의 집합을 결합하여 하나의 집합으로 만드는 병합 방법을 n-way 병합이라고 한다.

 

(1) 분할 : 입력 자료를 같은 크기의 부분집합 2개로 분할한다.

(2) 정복 : 부분집합의 원소들을 정렬한다. 부분집합의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법을 적용한다.

(3) 결합 : 정렬된 부분집합들을 하난의 집합으로 통합한다.

 

1. 정렬할 전체 자료의 집합에 대해서 최소 원소의 부분집합이 될 때까지 분할 작업을 반복하여 1개의 원소를 가진 부분집합 8개를 만든다.

2. 2개의 부분집합을 정렬하면서 하나의 집합으로 병합한다. 8개의 부분집합이 1개로 병합될 때까지 반복한다.

class Sort6{
	private int sorted[] = new int [30];
	public void merge(int a[], int m, int middle, int n) {
		int size = a.length;
		int i, j, k, t;
		i=m;
		j=middle+1;
		k=m;
		while(i<=middle && j<=n) {
			if(a[i] <= a[j]) sorted[k] = a[i++];
			else sorted[k] = a[j++];
			k++;
		}
		if(i>middle) {
			for(t=j ; t<=n ; t++, k++)
				sorted[k] = a[t];
		} else {
			for(t=m ; t<=middle ; t++, k++)
				sorted[k] = a[t];
		}
		for(t=m ; t<=n ; t++)
			a[t] = sorted[t];
		System.out.printf("\n 병합 정렬 >> ");
		for(t=0 ; t<size ; t++)
			System.out.printf("%3d ", a[t]);
	}
	public void mergeSort(int a[], int m, int n) {
		int middle;
		if(m<n) {
			middle = (m+n)/2;
			mergeSort(a, m, middle);
			mergeSort(a, middle+1, n);
			merge(a, m, middle, n);
		}
	}
}

public class mergeA {

	public static void main(String[] args) {
		int a[] = {69, 10, 30, 2, 16, 8, 31, 22};
		int size = a.length;
		Sort6 S = new Sort6();
		System.out.printf("\n정렬할 원소 : ");
		for(int i=0 ; i<a.length ; i++) {
			System.out.printf(" %d", a[i]);
		}			
		System.out.println();
		S.mergeSort(a, 0, size-1);

	}

}