4. 병합정렬(Merge Sort)

간만에 포스팅입니다. 처음 목표는 1일 1포스팅이었는데, 그것도 잠시 이리도 게을러지는군요. 얼른 Angular나 Spring도 포스팅해야하는데... 요새는 간단한 알고리즘 관련 포스팅만 진행하게 되네요.

암튼 오늘은 merge sort입니다. Quick Sort와 더불어 n log n의 성능을 내는 대표적인 정렬 방법입니다. 이름에서 알 수 있듯이 병합을 하면서 정렬을 하는겁니다. 그럼 gif를 통해 한번 살펴보겠습니다.

출처 : wikipedia.org

     . 우선 하나의 list를 계속해서 2 묶음으로 쪼갭니다.

     . 그리해서 하나의 element만 가지게 되면 병합을 실행합니다.

     . 병합을 할 때, 2 묶음씩 하게 되는데 이 때 작은것부터 병합을 해서 정렬을 하게 됩니다.

이해가 되셨죠? 이렇게 병합하는 과정에서 정렬을 실행하는 것을 merge sort라고 합니다. 딱 보니깐 같은 것을 반복하고 그걸 받아서 또 반복합니다.

그러니깐 quick sort에서처럼 재귀함수를 사용하면 될것 같습니다. 우선 pseudo code를 보겠습니다.

split each element into partitions of size 1
recursively merge adjancent partitions
  for i = leftPartStartIndex to rightPartLastIndex inclusive
    if leftPartHeadValue \gt;= rightPartHeadValue
      copy leftPartHeadValue
    else: copy rightPartHeadValue
copy elements back to original array

참 제가 pseudo code 출처를 안 밝혔었는데요. 모든 pseudo code는 visualgo.net에서 가져왔습니다.

     . 우선 size가 1이 될 때까지 쪼갭니다.

     . 재귀적으로(?) 파티션들을 병합합니다.

     . 이 때, a 그룹, b 그룹이 있을 때, a그룹 인덱스를 쭉, b 그룹 인덱스를 쭉 진행합니다.

     . a그룹과 b그룹중 작은 녀석을 병합 list에 넣습니다. 

그럼 바로 테스트 코드를 작성해보겠습니다.

private int[] original_array = {6, 7, 5, 8, 9, 0, 1, 3, 2, 4};
private int[] sorted_array = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

private List<Integer> original_list = new ArrayList<>();
private List<Integer> sorted_list = new ArrayList<>();

@Before
public void setup() {
     for (int num : original_array) original_list.add(num);
     for (int num : sorted_array) sorted_list.add(num);
}
    
@Test
public void mergeSortTest() {
     List<Integer> list = Sort.mergeSort(original_list);
     assertThat(list, is(sorted_list));
}

뭐, quicksort 테스트와 동일합니다. 그럼 이 테스트를 통과할 수 있는 merge sort 코드를 보겠습니다.

public static List<Integer> mergeSort(List<Integer> list) {
     if (list.size() < 2) return list;
    
     int mid = list.size()/2;
    
     List<Integer> a_list = new ArrayList<>();
     List<Integer> b_list = new ArrayList<>();
    
     for (int i=0; i<mid; i++) {
          a_list.add(list.get(i));
     }
     for (int i=mid; i<list.size(); i++) {
          b_list.add(list.get(i));
     }
    
     a_list = mergeSort(a_list);
     b_list = mergeSort(b_list);
    
     List<Integer> result = merge(a_list, b_list);
    
     return result;
}

private static List<Integer> merge(List<Integer> a_list, List<Integer> b_list) {
     int indexOfA = 0, indexOfB = 0;
     List<Integer> result = new ArrayList<>();
    
     while (indexOfA < a_list.size() && indexOfB < b_list.size()) {
          if (a_list.get(indexOfA) <= b_list.get(indexOfB)) {
               result.add(a_list.get(indexOfA));
               indexOfA++;
          } else {
               result.add(b_list.get(indexOfB));
               indexOfB++;
          }
     }
    
     while (indexOfA < a_list.size()) {
          result.add(a_list.get(indexOfA));
          indexOfA++;
     }
     while (indexOfB < b_list.size()) {
          result.add(b_list.get(indexOfB));
          indexOfB++;
     }
    
     return result;
} 

     . mergeSort에서는 하나의 list를 둘로 나눕니다.

     . 둘로 나뉜 list는 각자 또 다른 mergeSort를 수행합니다.

     . mergeSort가 완료된 list들끼리 병합을 수행합니다.

     . 병합할 때는 a리스트와 b리스트를 앞에서부터 쭉 살펴보면서 작은 녀석을 차례로 넣습니다.

어렵지 않죠? 다시금 마음 잡고 포스팅을 열심히 해봅시다. 다들 즐코딩:)

(하루에도 열두번도 더 다짐을 하지만, 쉽지가 않네요)

출처 : wikipedia.org