병합 정렬 (Merge sort)

병합 정렬 (Merge Sort)

병합 정렬은 분할 정복 (divide and conquer) 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘이다. 병합 정렬의 시간 복잡도 평균값은 O(nlogn)이다.

 

https://www.geeksforgeeks.org/merge-sort/

 

그룹을 병합하는 방법은 투 포인터 개념을 사용하여 왼쪽 포인터와 오른쪽 포인터의 값을 비교하고 작은 값을 결과 배열에 추가한 후 포인터를 오른쪽으로 1칸 이동시키면 된다. 

 

위의 예로 보면, [27, 38] 과 [10, 43] 을 병합해야 할 때 data 1 index와 data 2 index를 둔 후 index1은 첫 배열의 첫 번째 요소를, index2는 두 번째 배열의 첫 번째 요소를 가리킨 후 값을 비교한다. 27과 10중에 10이 더 작으므로 이를 새로운 배열의 첫 번째 값으로 저장하고 해당 인덱스 즉 index2를 하나 증가시킨다. 이는 43을 가리키게 되고, index1이 가리키는 27이 더 작으므로 다음 값으로 27이 넘어가며 index1++이 된다. 38이 43보다 작아 다음 값으로 배열에 들어가고 마지막으로 남은 하나의 값인 43이 자동으로 마지막에 저장된다. 그럼 결과는 10, 27, 38, 43 순서로 오름차순 정렬이 완료된다. 

 

단점

- 병합 과정에서 새로운 배열이 필요하므로 추가적인 공간이 요구된다. O(n)

- 제자리 정렬 (in-place sorting, 추가적인 메모리 공간 없이 정렬 가능한 알고리즘)이 아니다.

 

장점

- 안정적인 정렬 방법. 데이터의 분포에 영향을 덜 받아 입력 데이터가 무엇이든 정렬 시간은 동일하다.

 

 

시간 복잡도 계산

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

 

각 합병 단계의 비교 연산이 n번, (가로) 순환 호출의 깊이가 logn이므로 이 둘을 곱한 nlogn이 시간 복잡도가 된다.

 

병합 정렬은 코딩 테스트의 정렬 관련 문제에서 자주 등장한다. 특히 2개의 그룹을 병합하는 원리는 꼭 숙지해야 한다. 

---

 

[백준 2751번] 수 정렬하기 2

https://www.acmicpc.net/problem/2751

 

import java.io.*;
import java.util.*;

public class Main {
    public static int[] arr, tmp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        arr = new int[N + 1];
        tmp = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        mergeSort(1, N);     // 합병 정렬
        for (int i = 1; i <= N; i++) {
            bw.write(arr[i] + "\n");
        }
        bw.flush();
        bw.close();
    }

    private static void mergeSort(int s, int e) {
        if(e-s < 1)
            return;
        int m = s + (e-s) / 2;

        mergeSort(s, m);
        mergeSort(m+1, e);
        for (int i = s; i <= e; i++) {
            tmp[i] = arr[i];
        }
        int k = s;
        int index1 = s;
        int index2 = m+1;
        while(index1 <= m && index2 <= e) {     // 두 그룹 병합
            // 양쪽 그룹의 index가 가리키는 값을 비교해 더 작은 수를 선택해 배열에 저장하고, 선택된 데이터의 index 값 오른쪽으로 한 칸 이동하기
            if(tmp[index1] > tmp[index2]) {
                arr[k] = tmp[index2];
                k++;
                index2++;
            } else {
                arr[k] = tmp[index1];
                k++;
                index1++;
            }
        }
        while(index1 <= m){     // 한쪽 그룹이 모두 선택된 후 남아 있는 값 정리
            arr[k] = tmp[index1];
            k++;
            index1++;
        }
        while(index2 <= e) {
            arr[k] = tmp[index2];
            k++;
            index2++;
        }
    }
}

 

 

위의 코드는 Top-Down 방식으로 재귀 함수를 이용한 풀이이다. 두 부분으로 짤라 들어가며 서브 문제를 해결하는 방식이 가장 일반적이다. 그러나 대부분의 경우 정렬 과정은 최대한 재귀는 피하여 구현해주는 것이 일반적이기 때문에 아래의 Bottom-Up 으로 구현하는 게 좋다.

 

public class Merge_Sort {
 
	private static int[] sorted;		// 합치는 과정에서 정렬하여 원소를 담을 임시배열
	
	public static void merge_sort(int[] a) {
		
		sorted = new int[a.length];
		merge_sort(a, 0, a.length - 1);
		sorted = null;
	}
	
	// Bottom-Up 방식 구현
	private static void merge_sort(int[] a, int left, int right) {
		
		/*
		 * 1 - 2 - 4 - 8 - ... 식으로 1부터 서브리스트를 나누는 기준을 두 배씩 늘린다.
		 */
		for(int size = 1; size <= right; size += size) {
			
			/*
			 * 두 부분리스트을 순서대로 병합해준다.
			 * 예로들어 현재 부분리스트의 크기가 1(size=1)일 때
			 * 왼쪽 부분리스트(low ~ mid)와 오른쪽 부분리스트(mid + 1 ~ high)를 생각하면
			 * 왼쪽 부분리스트는 low = mid = 0 이고,
			 * 오른쪽 부분리스트는 mid + 1부터 low + (2 * size) - 1 = 1 이 된다.
			 *  
			 * 이 때 high가 배열의 인덱스를 넘어갈 수 있으므로 right와 둘 중 작은 값이
			 * 병합되도록 해야한다. 
			 */
			for(int l = 0; l <= right - size; l += (2 * size)) {
				int low = l;
				int mid = l + size - 1;
				int high = Math.min(l + (2 * size) - 1, right);
				merge(a, low, mid, high);		// 병합작업
			}
		}		
	}
	
	/**
	 * 합칠 부분리스트는 a배열의 left ~ right 까지이다. 
	 * 
	 * @param a		정렬할 배열
	 * @param left	배열의 시작점
	 * @param mid	배열의 중간점
	 * @param right	배열의 끝 점
	 */
	private static void merge(int[] a, int left, int mid, int right) {
		int l = left;		// 왼쪽 부분리스트 시작점
		int r = mid + 1;	// 오른쪽 부분리스트의 시작점 
		int idx = left;		// 채워넣을 배열의 인덱스
		
		
		while(l <= mid && r <= right) {
			if(a[l] <= a[r]) {
				sorted[idx] = a[l];
				idx++;
				l++;
			}
			else {
				sorted[idx] = a[r];
				idx++;
				r++;
			}
		}
		
        while(r <= right) {
            sorted[idx] = a[r];
            idx++;
            r++;
        }
        while(l <= mid) {
            sorted[idx] = a[l];
            idx++;
            l++;
        }
		
		/*
		 * 정렬된 새 배열을 기존의 배열에 복사하여 옮겨준다.
		 */
		for(int i = left; i <= right; i++) {
			a[i] = sorted[i];
		}
	}
}

 

병합하는 부분(merge())의 내용은 같다. 

 

---

 

 

[백준 1517번] 버블 소트

https://www.acmicpc.net/problem/1517

 

N의 최대 범위가 500,000이므로 O(nlogn)의 시간 복잡도로 정렬을 수행하면 된다. 이 문제는 버블 소트를 사용하면 제한 시간을 초과하므로 병합 정렬을 사용해야 한다. 병합 정렬에서 두 그룹을 병합하는 과정에 버블 정렬의 swap이 포함되어 있기 때문이다.

 

[24, 32, 42, 60]과 [5, 15, 45, 90]을 병합 정렬할 때, 뒤쪽 그룹의 5가 앞쪽 그룹의 24, 32, 42, 60 앞에 놓이는데 이는 버블 정렬에서 swap을 4번해야 볼 수 있는 효과이다. 마찬가지로 45는 60보다 앞에 놓이므로 버블 정렬에서 swap을 1번한 것과 동일하다. 이런 식으로 뒤의 원소가 앞의 원소보다 먼저 놓이게 될 때 이동하는 횟수만큼을 정답 변수에 더해주면 총 swap의 수를 구할 수 있다.

 

코드는 swap 횟수를 세기 위한 로직을 추가한 것만 제외하면 동일하다.

 

[정답]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class P1517_버블소트2 {
  public static int[] A, tmp;
  public static long result;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    A = new int[N + 1];
    tmp = new int[N + 1];
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i = 1; i <= N; i++) {
      A[i] = Integer.parseInt(st.nextToken());
    }
    result = 0;
    merget_sort(1, N); //병합정렬 수행하기
    System.out.println(result);
  }

  private static void merget_sort(int s, int e) { 
    if (e - s < 1)
      return;
    int m = s + (e - s) / 2;
    //재귀함수 형태로 구현
    merget_sort(s, m); 
    merget_sort(m + 1, e);
    for (int i = s; i <= e; i++) {
      tmp[i] = A[i];
    }
    int k = s;
    int index1 = s;
    int index2 = m + 1;
    while (index1 <= m && index2 <= e) {  //두 그룹을 Merge 해주는 로직 
      if (tmp[index1] > tmp[index2]) {
        A[k] = tmp[index2];
        result = result + index2 - k; // 뒤쪽 데이터 값이 작아 선택되는 경우 결과 값 업데이트
        k++;
        index2++;
      } else {
        A[k] = tmp[index1];
        k++;
        index1++;
      }
    }
    while (index1 <= m) {
      A[k] = tmp[index1];
      k++;
      index1++;
    }
    while (index2 <= e) {
      A[k] = tmp[index2];
      k++;
      index2++;
    }

  }
}

 

 

 

[참고 자료]

- 알고리즘 코딩 테스트 자바편

- https://www.geeksforgeeks.org/merge-sort/

Merge Sort - Data Structure and Algorithms Tutorials - GeeksforGeeks

- https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

- https://st-lab.tistory.com/233

자바 [JAVA] - 합병정렬 / 병합정렬 (Merge Sort)