[Algorithm] Merge Sort

정렬 알고리즘은 CS 수업을 듣게 되면 꼭 한번씩은 접하게 되는 알고리즘일 것이다. CS 학생이 기본을 탄탄히 하기 위해서 꼭 들어야 할 과목을 뽑는다면, Data Structure과 Algorithm을 개인적으로 뽑을 것이다. 하지 아이러니한 것은 실무에 들어가면 High-End 언어들의 편리성으로 크게 고려하지 않거나 고민하지 않은체 개발하는 개발자들이 상당히 많다는 것이다. 하지만 시간이 점점 지날수록 소프트웨어 개발에 경력을 쌓다보면 절대 중요한 과목이며, 기본기가 아닐까 싶다. 그런 의미에서 본인도 알고리즘과 자료구조에 대해 다시 상기하는 마음으로 공부하기 시작했다.

본 포스트는 개인 스터디의 결과물로써 기록하고자 하는 목적과 동시에 가능하다면 많은 사람과 함께 지식 교류를 해보고자 하는 목적으로 블로그에 작성하기 되었다. 내용면에서 부족한 부분이나 틀린 부분이 있다면 주저말고 댓글을 달아주길 바란다.

 

Algorithm이 란?

본격적으로 Merge Sort 알리즘에 대해서 알아보기 전에 간단한 배경 지식을 언급하고 지나가야 할 것 같다. 알고리즘이란, ‘The Algorithm Design Manual’이라는 책을 보면 다음과 같이 정의하고 있다.

“An algorithm is a procedure to accomplish a specific task.”

“알고리즘이란 특정 Task를 완수하기 위한 과정이다.”

사실 소프트웨어 개발 뿐만이 아니라 실생활에서도 많은 일을 처리하기 위해서 여러 과정을 걸쳐 처리를 하고 있다. 하지만 왜 소프트웨어 개발 산업에서 알고리즘을 중요하게 여기는 이유는 한정적인 자원에서 (CPU 성능, 메모리 공간) 효율적으로 더 많은 일을 빠르게 처리하기 위함일 것이다. 같은 결과를 내는 코드를 짜더라도 어떤 방식(알고리즘)으로 짰느냐에 따라 성능과 사용자에게 주는 제품의 인상은 천지 차이이다. 하드웨어의 눈부신 발전으로 많은 개발자들은 크게 고민하지 않고 이득을 보았을지 모르지만, Big-Data 시대에 더 많은 데이터를 더욱 안정적이며 신속하게 전달하기 위해서는 올바른 알고리즘 선택의 중요성을 더욱 실감할 수 있을 것이다.

 

Merge Sort

이제 본격적으로 본 포스트에서 다루고자 하는 Merge Sort에 대해서 설명해보겠다. 위에서 살펴보았지만 정렬 알고리즘 중에서 성능이 좋은 알고리즘 중에 하나로 뽑히는 Merge Sort는 평균과 최악의 경우 O(n log(n)) 만큼 런타임이 걸린다. 이 알고리즘은 배열을 반으로 쪼개고 쪼개어 각각의 절반을 비교하며 합병하면서 정렬하는 방식이다.

그럼 콘셉트를 백번 설명하는 것 보다 코드를 한번 보면서 설명하는 것이 이해를 돕는 것이 헐씬 쉬울 것으로 예상이 된다. 다름은 Objective-C로 짠 Merge sort 알고리즘이다.

  1. - (NSArray *)mergeSort:(NSArray *)unsortedArr
  2. {
  3.     NSInteger numOfItems = unsortedArr.count;
  4.  
  5.     //#1.
  6.     if (numOfItems < 2)
  7.         return unsortedArr;
  8.  
  9.     //#2.
  10.     NSInteger middle = numOfItems / 2;
  11.     NSRange left = NSMakeRange(0, middle);
  12.     NSRange right = NSMakeRange(middle, numOfItems – middle);
  13.  
  14.     //#3.
  15.     NSArray *leftArr = [unsortedArr subarrayWithRange:left];
  16.     NSArray *rightArr = [unsortedArr subarrayWithRange:right];
  17.  
  18.     //#4.
  19.     return [self merge:[self mergeSort:leftArr]
  20.               andRight:[self mergeSort:rightArr]];
  21. }
  22.  
  23. - (NSArray *)merge:(NSArray *)leftArr andRight:(NSArray *)rightArr
  24. {
  25.     //#5.
  26.     NSInteger resultArrCapa = leftArr.count + rightArr.count;
  27.     NSMutableArray *resultArr = [[NSMutableArray alloc]
  28.                                  initWithCapacity:resultArrCapa];
  29.     //#6.
  30.     NSInteger left = 0;
  31.     NSInteger right = 0;
  32.  
  33.     //#7.
  34.     while (left < leftArr.count && right < rightArr.count)
  35.     {
  36.         //#8.
  37.         NSComparisonResult compareResutl = [leftArr[left]
  38.                                             compare:rightArr[right]];
  39.  
  40.         //#9.
  41.         if (compareResutl == NSOrderedAscending)
  42.             [resultArr addObject:leftArr[left++]];
  43.         else
  44.             [resultArr addObject:rightArr[right++]];
  45.     }
  46.  
  47.     //#10.
  48.     NSRange leftRange = NSMakeRange(left, leftArr.count – left);
  49.     NSRange rightRange = NSMakeRange(right, rightArr.count – right);
  50.     NSArray *newLetfArr = [leftArr subarrayWithRange:leftRange];
  51.     NSArray *newRightArr = [rightArr subarrayWithRange:rightRange];
  52.  
  53.     [resultArr addObjectsFromArray:newLetfArr];
  54.     [resultArr addObjectsFromArray:newRightArr];
  55.  
  56.     //#11.
  57.     return resultArr;
  58. }

 

코드 설명

먼저 크게 두 개의 메소드로 나누어 보았다. 첫 번째 ‘mergeSort:’는 배열을 반으로 쪼개주는 역할을 한다. 두 번째 ‘merge:andRight:’ 메서드는 두 개의 배열에 있는 각 요소들을 비교하여 정렬하여 합병해주는 메서드이다. 코드 한줄 한줄을 따라가며 설명하기 전에 알아둬야 할 점은 ‘mergeSort:’ 메서드는 배열에 속한 요소의 갯수가 하나가 될 때까지 재귀적으로 돌아간다는 점을 알면 어떻게 동작하는지 쉽게 알 수 있을 것이다.

  1. 배열의 요소의 갯수가 하나이면 반환을 해준다. 그러므로써 재귀적으로 반복의 종료를 한다.
  2. 인수로 들어 온 배열을 반으로 쪼개기 위해서 다음과 같은 변수를 만들어 준다.
  3. NSRange 객체를 통해 원본 배열을 두 개의 Sub-Array 쪼갠다.
  4. ‘mergeSort:’메서드에서 가장 눈여겨 봐야하는 부분이다. 쪼갠 왼쪽, 오른쪽 배열을 다시 쪼갤 수 있을 만큼 쪼개며, 각각의 반환된 배열을 ‘merge:andRight:’로 넘겨준다.
  5. 합병하여 반환할 배열을 왼쪽 배열과 오른쪽 배열의 요소 갯수를 더한 만큼의 배열을 만들어준다.
  6. 왼쪽 배열과 오른쪽 배열의 요소들을 비교하기 위해서 사용할 인덱스 변수를 초기화 한다.
  7. 두 인덱스가 왼쪽 배열과 오른쪽 배열의 요소 갯수가 안넘는 선 안에서 while문으로 반복이 된다.
  8. 왼쪽 배열의 왼쪽 인덱스에 있는 값과 오른쪽 배열의 오른쪽 인덱스에 있는 값을 비교하여 NSComparisonResult 이넘 형 변수에 대입한다.
  9. 비교 결과 값 변수가 오름 차순이면 왼쪽 배열의 왼쪽 인덱스에 있는 값을 반환 배열에 넣어주고, 내림 차순이면 오른쪽 배열의 오른쪽 인덱스에 있는 값을 넣어준다.
  10. 왼쪽 배열과 오른쪽 배열을 비교하면서 합병을 했지만 한쪽 배열이 반환 배열에 다 들어가게 되면 분명 비교 되지 못한체 아직 기다리고 있는 요소들이 있을 것이다. 그 나머지 요소를 위해 다음과 같은 NSRange를 만들어서 남어지 요소를 반환 배열에 넣어준다.
  11. 정렬된 반환 배열을 전환해주면 메서드는 종료를 한다.

Merge Sort 알고리즘은 뛰어난 성능으로 정렬 알고리즘에서 유명한 알고리즘이다. 물론 실무에서 사용할 일이 정말 있을까 싶지만, 알고리즘을 이론으로만 알고있고, 구현해 본 경험이 없었다면 한번 시도해보길 권유한다. 좋은 알고리즘을 구현해보는 것은 생각보다 만만치 않은 일이지만, 실무하는데 있어서 얼마나 지금까지 생각을 깊게 하지 않고 편한데로만 짰었는지, 자신을 돌아보는 시간이 되지 않을까 싶다. 대학 시절 정말 싫어했던 알고리즘을 경력을 쌓고 다시 보니 지난 세월을 돌아보게하는 좋은 경험인 것 같다. 앞으로는 코드 하나를 짜더라도 한번 더 생각해보고 짜야겠다는 마음을 가져본다.