[Algorithm] 04.정렬 - 병합정렬 (Merge sort)

오늘은 네 번째 정렬 알고리즘이자, 시간 복잡도가 O(NlogN)인 첫 번째 정렬 알고리즘.

병합정렬에 대해 알아보겠습니다.

 

1. 데이터들이 한 개씩 쪼개어질 때까지 주어진 데이터를 두 개의 그룹으로 나누는 작업을 반복한다.

2. 하나씩 쪼개어진 데이터는 정렬된 상태가 된다.

3. 정렬된 데이터들을 쪼갠 역순으로 병합하면서 정렬하면 정렬된 상태의 전체 데이터를 구할 수 있다.

 

처음 병합정렬의 설명을 말로만 들으면 머릿속으로 정렬 과정을 그리기 쉽지 않을 텐데요.

그림을 통해 실제로 정렬이 이루어지는 과정을 보면서 설명하고 정리해드리도록 하겠습니다.

 

정렬 시작 전의 상태

언제나처럼 정렬되지 않은 데이터가 있습니다.

3, 5, 7, 4, 2, 6, 8, 1의 여덟 데이터를 정렬해보도록 하겠습니다.

우선 데이터들을 두 개의 그룹으로 나누는 과정을 반복하여, 하나씩 쪼개어줍니다.

이번 예시의 경우엔 데이터의 개수가 2^3인 8개이므로 3번의 단계를 거쳐서 쪼개어집니다.

이렇게 최종적으로 쪼개어진 밑단의 데이터들은 자연스럽게 정렬된 상태가 됩니다!

(데이터가 하나이기 때문에 당연히 정렬된 상태입니다.)

병합의 첫번째 단계

이제 부분적으로 정렬된 데이터들을 병합하는 첫번째 단계가 시작됩니다.

각각 정렬된 상태인 3과 5를 비교하여 병합합니다.

(두 데이터 그룹이 부분적으로 정렬된 상태이기때문에 앞에서부터 읽어들이면 됩니다.)

 

같은 방법으로 7과 4를 병합합니다.

병합의 첫번째 단계가 완료되었습니다.

이렇게 첫번째 병합이 완료되었습니다.

두번째 단계부턴 두개의 그룹이 병합되는 과정을 설명해보겠습니다.

병합의 두번째 단계

우리는 이미 부분적으로 정렬된 3,5 그리고 4,7의 그룹을 가지고 있습니다.

각 그룹이 이미 정렬된 상태기 때문에 전체를 탐색할 필요 없이 두 그룹의 가장 앞의 수를 보고 더 작은 수를 고르면 됩니다.

3과 4를 비교해 3을, 5와 4를 비교해 4를, 5와 7을 비교해 5, 마지막으로 남은 7을 골라줍니다.

자연스럽게 두개의 그룹이 정렬된 상태로 합쳐집니다.

그리고 두개의 그룹을 합칠 때 비교횟수는 전체 데이터의 갯수만큼이면 충분합니다!

(한 번의 비교에서 한개의 데이터가 골라집니다.)

 

같은 방법으로 나머지 그룹도 병합을 진행시켜줍니다.

 

마지막 세번째 병합 단계

이제 마지막, 세번째 병합을 똑같이 진행해줍니다.

두개의 그룹이 각각 부분적으로 정렬된 상태이기 때문에 앞에서부터 비교해가면서 합쳐주면 됩니다.

 

정렬이 완료되었습니다!

 

 

이렇게 병합정렬을 통한 정렬이 완료되었습니다!

이건 이해를 돕기 위한 예시일 뿐 실제 코드와 프로그램에선 재귀적으로 파고들어 가며 정렬이 진행되기 때문에 동작 흐름은 다릅니다.

 

병합정렬의 시간 복잡도가 왜 NlogN인지 간단하게 설명해보겠습니다.

앞서 배운 정렬들에서 우리는 각 단계마다 비교를 N, N-1, N-2... 번씩 수행하였고 N^2번의 비교가 필요함을 알았습니다.

병합정렬의 경우에는 각 단계별로 N번의 비교가 이루어집니다. 

하지만 이 단계는 N번 반복되는 것이 아니라, N의 Log2값을 취한 만큼 이루어집니다.

데이터가 2^10개인 1024개라고 생각해봅시다.

처음 분할 단계에서 데이터는 2개의 그룹으로 나뉘는 일을 10번 반복하여 1개씩 1024개로 쪼개집니다.

그리고 이 데이터들은 10번의 단계를 거쳐 정렬된 1024개의 데이터가 됩니다.

10 * 1024 = 10,240번의 비교를 통해 정렬이 완료되는 겁니다.

버블정렬의 경우 같은 데이터에 대해 523,776번의 비교가 필요한 걸 생각하면, 또 데이터의 개수가 늘어날수록 이 차이가 더 커질 거란 걸 생각하면 NlogN정렬 알고리즘들이 더 효율적인걸 알 수 있습니다.

 

아래는 JAVA로 구현한 간단한 병합정렬 코드와 테스트입니다!

ArrayList 자료구조를 이용해 만들어봤는데요, 제가 적당히 작성한 코드라 실제 효율적인 부분에선 좋지 않을 것 같습니다!

병합정렬의 작동원리를 이해한다 정도로만 봐주시면 감사하겠습니다!

이것저것 바꿔보고 디버깅하면서 흐름이 이해되시길 바랍니다.

 

import java.util.ArrayList;
import java.util.Random;

public class sort_04_merge {
	static int size = 10;
	static int bound = 1000;
	static int count = 0;
	// 데이터의 갯수와 범위 설정

	public static void main(String[] args) {
		ArrayList<Integer> data = new ArrayList<Integer>();
		Random random = new Random();

		for (int i = 0; i < size; i++) {
			data.add(random.nextInt(bound));
		}
		// 랜덤 값 넣어주기

		System.out.println(data.toString());
		// 랜덤하게 들어간 데이터 확인

		//////////////// 병합정렬 구현코드는 하단으로 /////////////////
		data = mergeSort(data);
		//////////////////////////////////////////////////////

		System.out.println(data.toString());
		System.out.println("비교횟수 : " + count);
	}

	private static ArrayList<Integer> mergeSort(ArrayList<Integer> list) {
		int size = list.size();
		ArrayList<Integer> mergeList = new ArrayList<>();

		if (size <= 1) {
			return list;
		} else {
			ArrayList<Integer> left = new ArrayList<>();
			ArrayList<Integer> right = new ArrayList<>();

			for (int i = 0; i < (size / 2); i++) {
				left.add(list.get(i));
			}
			for (int i = (size / 2); i < size; i++) {
				right.add(list.get(i));
			}

			left = mergeSort(left);
			right = mergeSort(right);

			//System.out.println("left : " + left.toString());
			//System.out.println("right : " + right.toString());

			for (int i = 0, l = 0, r = 0; i < size; i++) {
				if (r == right.size() || (l != left.size() && left.get(l) <= right.get(r))) {
					mergeList.add(left.get(l));
					l++;
				} else {
					mergeList.add(right.get(r));
					r++;
				}
				count++;
			}
			//System.out.println("merge : " + mergeList.toString());
			return mergeList;
		}
	}
}