병합 정렬 (Merge Sort)

퀵 정렬과 합병 정렬은 리스트를 분할하고 정복하는 방법으로 정렬한다.

 

이 두 가지 정렬은 특징은 다음과 같다.

 

퀵 정렬 : 평균 복잡도는 O(NlogN) 이지만 최악의 복잡도는 O(N^2)이다.

 

합병 정렬 : 시간 복잡도는 O(NlogN)을 보장한다. 하지만 정렬을 하기 위해서 임시 배열을 사용하기 때문에

 

추가적인 메모리가 필요하다.

 

[C++]

#include <iostream>
using namespace std;

// 병합정렬 특 : 추가적인 메모리를 요구함
int size = 8;
int sorted[8]; // 정렬 배열은 무조건 전역 변수로 선언

void merge(int a[], int m, int middle, int n) {
  int i = m;
  int j = middle + 1;
  int 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) { // i가 먼저 끝남
    for (int t = j; t <= n; t++)
      sorted[k++] = a[t];
  } else {
    for (int t = i; t <= middle; t++)
      sorted[k++] = a[t];
  }
  // 정렬된 데이터를 실제 배열로 삽입
  for (int t = m; t <= n; t++)
    a[t] = sorted[t];
}

// IDEA : 일단 정확히 반으로 나누고 나중에 정렬
void mergeSort(int a[], int m, int n) {
  // 크기가 1보다 큰 경우
  if (m < n) {
    int middle = (m + n) / 2;
    mergeSort(a, m, middle);
    mergeSort(a, middle + 1, n);
    merge(a, m, middle, n);
  }
}

int main(void) {
  int arr[size] = {7, 6, 5, 8, 3, 5, 9, 1};
  mergeSort(arr, 0, size - 1);
  for (int i = 0; i < size; i++)
    cout << arr[i] << " ";
  return 0;
}

 

[JAVA]

package MergeSort;

public class MergeSort {

    static void merge(int[] list, int left, int mid, int right, int size) {
        int[] storage = new int[size];
        int i = left;
        int j = mid + 1;
        int k = left;

        // 분할 정렬된 list 들의 합병
        while (i <= mid && j <= right) {
            if (list[i] <= list[j])
                storage[k] = list[i++];
            else
                storage[k] = list[j++];
            k++;
        }

        // 선택받지 못한 값들을 차례대로 채워 넣는다
        if (i > mid) {
            for (int l = j; l <= right; l++)
                storage[k++] = list[l];
        } else {
            for (int l = i; l <= mid; l++)
                storage[k++] = list[l];
        }

        // 임시 배열에 저장된 값을 원래 배열로 옮김
        for (int l = left; l <= right; l++)
            list[l] = storage[l];
        
    }

    static void merge_sort(int[] list, int left, int right, int size) {
        if (left < right) {
            int mid = (left + right) / 2;
            merge_sort(list, left, mid, size); // 기준 왼쪽 정렬
            merge_sort(list, mid + 1, right, size); // 기준 오른쪽 정렬
            merge(list, left, mid, right, size); // 양쪽 정렬된 리스트를 합친다
        }
    }

    public static void main(String[] args) {
        int[] list = new int[10000];
        int[] clist = new int[10000];
        int size = list.length;
        
        // 역순으로 값을 넣는다.
        for(int i=0;i<size;i++) {
            list[i] = size-i;
            clist[i] = size-i;
        }
        
        // 병합 정렬 속도 측정
        long st = System.currentTimeMillis();
        merge_sort(list, 0, size - 1, size);
        long et = System.currentTimeMillis();
        System.out.println("mergesort time(nlogn) : "+(et-st));
        
        // 버블 정렬  측정
        st = System.currentTimeMillis();
        for(int i=0;i<size-1;i++) {
            for (int j = i+1; j < size; j++) {
                if(clist[i]>clist[j]) {
                    int tmp = clist[j];
                    clist[j] = clist[i];
                    clist[i] = tmp;
                }
            }
        }
        
        et = System.currentTimeMillis();
        System.out.println("bubble sort time(n^2) : "+(et-st));

    }

}

 

 

 

Merge Sort(NlogN)  vs Bubble Sort(N^2)  속도 비교

 

배열 사이즈를 동적으로 바꿔가면서 배열의 값들을 역순으로 넣고 비교했다.

 

사이즈가 적을 때는 버블 소트가 속도가 확실히 빠르지만, 충분히 큰 사이즈를 넣어줬을 때 부터는 

 

병합 정렬이 확실히 빨랐다.

 

https://www.youtube.com/watch?v=YJ-OUnZu7nQ&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=9