230622 Today I Learned

오늘은 병합정렬에 대해 알아보고 구현해보았다.

분할정복(Divide and Conquer)

문제를 작은 부분 문제로 분할해 해결하는 알고리즘 설계 패러다임

• 큰 문제를 작은 부분 문제로 분할한 뒤, 부분문제를 해답을 최종적으로 결합해 전체 문제의 해답을 얻는 방법이다.

이미지 출처 : st-lab

병합정렬(Merge Sort)

분할정복 방식을 기반으로 배열을 최대한 작게 분할해 인접한 원소들 끼리 비교해 정렬하고 다시 합쳐서 정렬하는 정렬 알고리즘

• 정렬 과정(2-way)
  배열을 더이상 쪼갤 수 없는 크기가 1인 부분배열로 계속 분할한다. 부분배열을 두 개씩 합치면서 작은 숫자가 앞, 큰 숫자가 뒤로 가게 합친다. 각 부분배열에서 가장 작은 값끼리 비교해 계속 정렬하면서 합쳐간다. 원래 배열의 크기까지 최종적으로 다 합치면 정렬이 다 된다.

• 시간복잡도 : O(n log n) 배열을 절반으로 나누는 분할 단계가 O(log n), 각 배열을 병합하는 단계는 각 부분 배열의 모든 원소를 한 번씩 비교하면서 병합하므로 O(n)이므로 최종적으로 O(n log n)이된다.

• 공간복잡도 : O(n). 병합 결과를 담아 놓을 배열이 원래의 배열 크기 만큼 추가적으로 필요하므로 추가적인 메모리 사용이 있다.

• 장점 :
  안정 정렬이다.
  모든 경우에서 시간복잡도가 O(n log n)이므로 효율적이다.
  분할단계에서 부분 배열을 독립적으로 정렬하기 때문에 병렬 처리가 가능하다.

• 단점 :
  추가적인 메모리 공간이 필요하다. (공간복잡도 O(n))
  재귀 호출을 사용하기 때문에 이에따른 오버헤드나 스택오버플로우 문제가 있을 수 있다.

Java로 구현

배열을 크기가 1이 될때까지 다 분할하고, 왼쪽 오른쪽 배열을 차례대로 비교해 임시 배열에 정렬하면서 삽입해가고, 완료되면 원 배열을 임시배열로 대체해서 정렬 완료

import java.util.Arrays;
import java.util.Random;

public class A_MergeSort {

//  정렬 과정에서 사용할 임시 배열
  private static int[] tempArray;

  public static void mergeSort(int[] array){
    if (array.length < 2) return;

//    임시배열을 원본 배열의 사이즈로 만든다
    tempArray = new int[array.length];
    mergeSort(array, 0, array.length-1);
//    임시 배열의 용도가 다해서 null 처리한다.
    tempArray = null;

  }

  private static void mergeSort(int[] array, int left, int right){
//    left = right가 넘어가면 부분배열이 1개의 원소만 갖게되므로 종료한다.
    if (left >= right) return;

    int mid = (left + right) / 2;         // 절반위치

    mergeSort(array, left, mid);          // left~mid까지 왼쪽 부분 배열로 분할
    mergeSort(array, mid+1, right); // mid+1~right까지 오른쪽 부분 배열로 분할

    merge(array, left, mid, right);       // 분할된 배열을 병합
  }

  private static void merge(int[] array, int left, int mid, int right){
    int l = left;       // 왼쪽 부분 배열의 시작 인덱스
    int r = mid + 1;    // 오른쪽 부분 배열의 시작 인덱스
    int i = left;       // 임시 배열에 채워넣을 인덱스

//    왼쪽, 오른쪽 부분 배열이 둘다 남아있을때
    while (l <= mid && r <= right){
//      왼쪽이 더 작으면 왼쪽껄 임시 배열에 삽입
      if (array[l] <= array[r]){
        tempArray[i] = array[l];
        i++;
        l++;
//        오른쪽이 더 작으면 오른쪽껄 임시 배열에 삽입
      } else {
        tempArray[i] = array[r];
        i++;
        r++;
      }
    }

//    왼쪽 부분배열이 임시배열에 다 들어갔을 때
    if (l > mid){
//      오른쪽 부분배열이 남아있으면 남은 오른쪽 배열을 임시배열에 삼입
      while (r <= right){
        tempArray[i] = array[r];
        i++;
        r++;
      }
//      오른쪽 부분배열이 임시배열에 다 들어갔을 때
    } else {
//      왼쪽 부분배열이 남아있으면 남은 왼쪽 배열을 임시뱅려에 삽입
      while (l <= mid) {
        tempArray[i] = array[l];
        i++;
        l++;
      }
    }
//   부분배열이 모두 임시배열에 들어가면 원래 배열을 임시배열로 대체
    for (int j = left; j <= right; j++) {
      array[j] = tempArray[j];
    }

  }

  public static void main(String[] args) {
    Random random = new Random();
    int[] array = new int[10];
    for (int i = 0; i < array.length; i++) {
      array[i] = random.nextInt(100); // 0~99까지 정수 랜덤
    }

    System.out.print("정렬 전 배열 : ");
    System.out.println(Arrays.toString(array));
    System.out.println("-----------------------------------------");
    mergeSort(array);
    System.out.print("병합정렬 후 배열 : ");
    System.out.println(Arrays.toString(array));
    System.out.println("-----------------------------------------");
  }
}