정렬2 (단순 삽입 정렬, 병합 정렬)

단순 삽입 정렬

단순 삽입 정렬은 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 삽입하는 작업을 반복하여 정렬하는 알고리즘 입니다.

 

단순 삽입 정렬은 2번째 요소부터 선택하여 진행합니다.

 

4는 6보다 앞에 위치해야 하므로 앞쪽에 삽입합니다.

 

다음 3번째 요소인 1을 선택해 앞쪽에 삽입합니다. 그 이후에도 계속해서 같은 작업을 수행합니다.

그림에서 볼 수 있듯이 정렬된 부분과 아직 정렬되지 않은 부분에서 배열이 다시 구성된다고 생각하면서 작업을 n-1번 반복하면 정렬을 마치게 됩니다.

 

• 아직 정렬되지 않은 부분의 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입합니다.

package chap06;
import java.util.Scanner;
// 단순 삽입 정렬

class InsertionSort {
	// 단순 삽입 정렬
	static void insertionSort(int[] a, int n) {
		for (int i = 1; i < n; i++) {
			int j;
			int tmp = a[i];
			for (j = i; j > 0 && a[j - 1] > tmp; j--)
				a[j] = a[j - 1];
			a[j] = tmp;
		}
	}

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);

		System.out.println("단순 삽입 정렬");
		System.out.print("요솟수：");
		int nx = stdIn.nextInt();
		int[] x = new int[nx];

		for (int i = 0; i < nx; i++) {
			System.out.print("x[" + i + "]：");
			x[i] = stdIn.nextInt();
		}

		insertionSort(x, nx);				// 배열 x를 단순 삽입 정렬

		System.out.println("오름차순으로 정렬했습니다.");
		for (int i = 0; i < nx; i++)
			System.out.println("x[" + i + "]＝" + x[i]);
	}
}

 

단순 정렬의 시간 복잡도

 

이렇게 구현한 단순 삽입 정렬 알고리즘은 떨어져 있는 요소들이 서로 뒤바뀌지 않아 안정적입니다.

요소의 비교횟수와 교환 횟수는 n^2 / 2 회이므로 시간복잡도는 O(n^2) 입니다.

 

병합 정렬

병합 정렬은 배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘입니다.

 

정렬을 마친 배열의 병합

사진처럼 배열 a,b 가 있다고 가정했을때 두 배열을 정렬하여 저장할 배열 c에 병합 정렬하는 과정입니다.

 

배열 a,b,c를 스캔할 때 선택한 요소의 인덱스는 pa,pb,pc 입니다.

이 인덱스를 저장한 변수를 지금부터 커서라고 하겠습니다. (처음에는 첫요소를 선택하기 때문에 모두 0으로 초기화)

 

1. 배열 a에서 선택한 요소(a[pa])와 배열 b에서 선택한 요소(a[pb])를 비교하여 작은 값을 c[pc]에 저장합니다. 그런 다음 커서 pc와 작은 값이 존재하는 배열의 커서를 한칸 옮기고 다시 pa와 pb를 비교하여 작은 값을 저장하는 과정을 반복 합니다. 커서 pa 가 a의 끝에 다다르거나 커서 pb가 b의 끝에 다다르면 이 작업을 종료합니다.
2. while문의 실행 조건은 1의 과정을 통해 하나의 배열은 모두 배열c로 복사되고 나머지 하나의 배열은 아직 복사하지 않은 요소가 남아 있습니다. 남아 있는 배열은 커서를 한칸씩 진행하면서 나머지 요소를 배열 c에 복사합니다.

package chap06;
import java.util.Scanner;
// 정렬을 마친 배열의 병합

class MergeArray {
	// 정렬을 마친 배열 a, b를 병합하여 배열 c에 저장합니다. 
	static void merge(int[] a, int na, int[] b, int nb, int[] c) {
		int pa = 0;
		int pb = 0;
		int pc = 0;

		while (pa < na && pb < nb)	// 작은 값을 저장합니다.
			c[pc++] = (a[pa] <= b[pb]) ? a[pa++] : b[pb++];

		while (pa < na)				// a에 남아 있는 요소를 복사합니다.
			c[pc++] = a[pa++];

		while (pb < nb)				// b에 남아 있는요소를 복사합니다.
			c[pc++] = b[pb++];
	}

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		int[] a = {2, 4, 6, 8, 11, 13};
		int[] b = {1, 2, 3, 4, 9, 16, 21};
		int[] c = new int[13];

		System.out.println("두 배열의 병합");

		merge(a, a.length, b, b.length, c);	  // 배열 a와 b를 병합하여 c에 저장

		System.out.println("배열 a와 b를 병합하여 배열 c에 저장했습니다.");
		System.out.println("배열 a：");
		for (int i = 0; i < a.length; i++)
			System.out.println("a[" + i + "] = " + a[i]);

		System.out.println("배열 b：");
		for (int i = 0; i < b.length; i++)
			System.out.println("b[" + i + "] = " + b[i]);

		System.out.println("배열 c：");
		for (int i = 0; i < c.length; i++)
			System.out.println("c[" + i + "] = " + c[i]);
	}
}

위 코드는 3개의 반복문을 늘어놓는 단순한 알고리즘으로 구현되어 있습니다.

병합에 필요한 시간 복잡도는 O(n)입니다.

 

병합 정렬

정렬을 마친 배열의 병합을 응용하여 분할 정복법에 따라 정렬하는 알고리즘을 병합 정렬이라고 합니다.

 

사진은 병합 정렬 과정을 간단히 나타낸 것으로, 먼저 배열을 앞부분과 뒷부분을 나눕니다.

여기서는 배열의 길이가 12이기 때문에 6개의 배열로 각각 나눕니다.

나눈 두 배열을 각각 정렬을 하고 병합하면 배열 모두를 정렬할 수 있습니다.

 

이 때 앞뒤에 놓인 6개의 요소를 정렬할 때는 그냥 정렬하는 것이 아니라 다시 병합 정렬을 적용합니다.

예를 들어 뒷부분은 위 사진처럼 정렬합니다. 여기서 만들어지는 [9,0,1]과 뒷 부분[5,2,3]도 같은 순서에 따라 정렬합니다.

 

package chap06;
import java.util.Scanner;
// 병합 정렬

class MergeSort {
	static int[] buff;	// 작업용 배열

	// a[left] ~ a[right]를 재귀적으로 병합 정렬 
	static void __mergeSort(int[] a, int left, int right) {
		if (left < right) {
			int i;
			int center = (left + right) / 2;
			int p = 0;
			int j = 0;
			int k = left;

			__mergeSort(a, left, center);			// 배열의 앞부분을 병합 정렬합니다.
			__mergeSort(a, center + 1, right);		// 배열의 뒷부분을 병합 정렬합니다.

			for (i = left; i <= center; i++)
				buff[p++] = a[i];

			while (i <= right && j < p)
				a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];

			while (j < p)
				a[k++] = buff[j++];
		}
	}

	// 병합 정렬
	static void mergeSort(int[] a, int n) {
		buff = new int[n];				// 작업용 배열을 생성합니다.

		__mergeSort(a, 0, n - 1);		// 배열 전체를 병합 정렬합니다.

		buff = null;					// 작업용 배열을 해제합니다.
	}

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);

		System.out.println("병합 정렬");
		System.out.print("요솟수：");
		int nx = stdIn.nextInt();
		int[] x = new int[nx];

		for (int i = 0; i < nx; i++) {
			System.out.print("x[" + i + "]：");
			x[i] = stdIn.nextInt();
		}

		mergeSort(x, nx);		// 배열 x를 병합 정렬합니다.

		System.out.println("오름차순으로 정렬했습니다.");
		for (int i = 0; i < nx; i++)
			System.out.println("x[" + i + "]＝" + x[i]);
	}
}

배열 병합의 시간 복잡도는 O(n)이고 데이터의 요소 개수가 n개 일 때, 병합 정렬의 단계는 log n 만큼 필요하므로 전체 시간 복잡도는 O(n log n)이라고 할 수 있습니다. 병합 정렬은 서로 떨어져 있는 요소를 교환하는 것이 아니므로 안정적인 정렬 방법이라고 할 수 있습니다.