Algorithm/정렬 알고리즘

병합 정렬 (Merge Sort)

너지살 2023. 12. 31. 18:59

 

원하는 기준에 맞춰 자료를 다시 나열하는 정렬 알고리즘

 

 

 

병합 정렬 (Merge Sort)

병합 정렬은 분할 정복 알고리즘으로 평균적으로 효율적인 정렬 방법입니다. 

병합 정렬은 배열을 더 이상 나눌 수 없을 때까지 반으로 나눕니다. 나눈 배열을 정렬하고 병합하면서 전체 배열의 정렬을 완성합니다. 

 

시간 복잡도 : O(n log n) 

 

반으로 나누면서 진행하기 때문에 시간 복잡도는 O(n log n)입니다. 최악의 상황에서도 O(n log n)입니다. 

 

평균적인 속도는 퀵 정렬 > 힙 정렬 > 병합 정렬 입니다. 

 

 

장점

  • 안정적인 정렬 : 같은 값의 요소가 정렬 후에도 순서를 유지합니다.
  • 일정한 시간 복잡도 : 모든 경우에 대해 O(n log n)입니다. 데이터에 관계없이 일정한 성능을 보장합니다. 
  • 대규모 데이터에 효율적 : 크기가 큰 데이터에서 효율적입니다. 

 

단점

  • 추가적인 메모리 필요 : 추가 배열을 사용하기 때문에 O(n)의 공간이 필요합니다. 
  • 비교적 느린 속도 : 병합 정렬은 퀵 정렬 같은 다른 정렬 알고리즘에 비해 상대적으로 느린 편입니다. 작은 데이터 세트에 대해 더 효율적인 알고리즘이 있습니다. 

 

이러한 장단점을 고려하여, 병합 정렬은 메모리 사용량이 문제가 되지 않고, 안정적인 정렬이 필요하며 데이커 크기가 큰 경우에 적합한 알고리즘 입니다. 

 

 

 

동작 과정

1. 분할 : 배열을 계속 반으로 나눕니다. 분할 과정은 부분 리스트가 하나의 요소만 가질 때까지 계속됩니다. 하나의 요소를 가진 리스트는 정렬되었다고 간주합니다. 

 

2. 결합 정렬 : 분할된 배열을 다시 병합하면서 정렬합니다. 두 개의 배열에서 요소들을 올바른 순서로 병합하여 배열을 정렬합니다. 전체 배열로 합쳐질 때까지 계속합니다. 

 

 

즉 요소가 하나가 될때까지 반씩 분할하는데 필요한 단계의 수는 O(log n)입니다.

병합 단계에서각 단계에서 모든 요소를 한 번씩 비교하여 O(n)이 됩니다.

총 O(log n) 단계가 있고 각 단계마다 비교하면 O(n)이 걸리므로 전체 시간 복잡도는 O(n log n)이 됩니다. 

 

 

 

 

예시

원본 배열 : [38, 27, 43, 3, 9, 82, 19] 

 

 

분할 단계 : 배열을 반으로 계속 나누어 하나의 요소가 될 때까지 나눕니다. 

[38, 27, 43, 3]  [9, 82, 19] 

[38, 27] [43, 3] [9, 82] [19]

[38] [27] [43] [3] [9] [82] [19]

 

 

 

병합 정렬 : 인접한 두 배열의 정렬하면서 병합합니다. 이 때, 각 첫 번째 자리의 비교하여 낮은 숫자부터 앞으로 배치합니다.

 

[38] [27]을 정렬하면서 병합 

 

[38]

[27] 

[]

각 배열의 첫 번째 숫자 중 작은 것을 먼저 나오게 합니다. 38과 27중 27이 나옵니다.

 

[38]

[]

[27]

 

배열에 더 이상 없으므로 38이 나옵니다.

[]

[]

[27, 38] 

 

총 배열은 다음과 같이 됩니다.

[27, 38] [43, 3] [9, 82] [19]

 

[43] [3] 도 정렬하면서 병합하면 [3, 43]이 됩니다. 

 

 

[27, 38] [3, 43] 정렬하면서 병합

 

[27, 38]

[3, 43] 

결과 배열 : []

두 개의 배열에서 첫 번째 숫자를 비교하합니다. 3이 더 작으므로 3이 먼저 나옵니다. 

 

[27, 38]

[43]

결과 배열 : [3] 

 

첫 번째 숫자를 비교하면 27이 작으므로 27이 나옵니다. 

[38]

[43]

결과 배열 : [3, 27] 

 

다음 두 배열의 첫 번째 숫자를 비교하면 38이 작으므로 38이 나옵니다. 

[]

[43]

결과 배열 : [3, 27, 38]

 

위의 배열이 비었으므로 나머지 배열의 값들을 넣습니다.

[]

[]

결과 배열 : [3, 27, 38, 43] 

 

이런 식으로 부분적으로 정렬하면서 병합하여 최종적으로 정렬된 배열을 완성합니다. 

 

최종 정렬 배열 : [3, 9, 19, 27, 38, 43, 82]

 

 

 

 

 

 

Java 구현 코드

/*
병합 정렬

참고 영상 : https://www.youtube.com/watch?v=QAyl79dCO_k
 */
public class MergeSort {

  public static void main(String[] args) {
    int[] array = {38, 27, 43, 3, 9, 82, 19};
    printArray(array);
    mergeSort(array);
    printArray(array);
  }

  // 병합 정렬 시작
  public static void mergeSort(int[] array) {
    int[] temp = new int[array.length];
    mergeSort(array, temp, 0, array.length - 1);
  }

  // 병합 정렬 재귀
  public static void mergeSort(int[] array, int[] temp, int start, int end) {
    if(start < end) {
      // 배열을 반으로 나눔
      int mid = (start + end) / 2;

      // 재귀를 통해 정렬
      mergeSort(array, temp, start, mid);
      mergeSort(array, temp, mid+1, end);

      // 정렬된 왼쪽과 오른쪽을 합치는 함수
      merge(array, temp, start, mid, end);
    }
  }

  // 정렬된 왼쪽과 오른쪽을 합치는 함수
  public static void merge(int[] array, int[] temp, int start, int mid, int end) {
    // 임시 저장소에 왼쪽과 오른쪽을 저장
    for(int i = start; i <= end; i++) {
      temp[i] = array[i];
    }

    int part1 = start; // 왼쪽의 시작지점
    int part2 = mid + 1; // 오른쪽의 시작지점
    int index = start; // 결과 배열에 저장될 인덱스

    // 왼쪽과 오른쪽을 비교해서 작은 것부터 결과 인덱스에 저장
    while(part1 <= mid && part2 <= end) {
      // 왼쪽이 작을 경우
      if(temp[part1] <= temp[part2]) {
        array[index] = temp[part1];
        part1++;
      }
      // 오른쪽이 작을 경우
      else {
        array[index] = temp[part2];
        part2++;
      }
      // 왼쪽, 오른쪽 상관없이 결과 index는 +1이 된다.
      index++;
    }

    // 왼쪽에 남은 부분을 저장한다. (오른쪽이 남았을 경우는 이미 배열 뒤쪽에 배치되어 있다.)
    for(int i = 0; i <= mid-part1; i++) {
      array[index + i] = temp[part1 + i];
    }
  }

  public static void printArray(int[] array) {
    for(int number : array) {
      System.out.print(number + " ");
    }
    System.out.println();
  }

}

 

 

 

 

 

마무리

이번에는 일정한 성능을 발휘하는 병합 정렬을 정리했습니다.

다음에는 Heap 자료 구조로 배열의 정리하여 정렬하는 힙 정렬을 정리하겠습니다.

감사합니다.