[MIT 6.006 정리] Lec 03. (이진 탐색,) 삽입 정렬, 병합 정렬

* 본 포스팅은 기본적으로 edwith 플랫폼을 통해 제공되고 있는 MIT 6.006 Introduction to Algorithms (Fall 2011) 강의 내용을 바탕으로 정리한 것입니당 :D

 

------- * ------- * ------- * -------

 

* Why sorting?

• 자료의 효율적인 관리를 위해 (예: 전화번호부. 향후 검색에 용이)
• 일단 자료가 정렬되고 나면 훨씬 해결하기 쉬워지는 문제들이 있음 (예: 중간값(median) 찾기)
• 정렬이 데이터 압축 등 다양한 프로그램의 서브-루틴(sub routine) 으로 사용되기도 함 (예: 컴퓨터 그래픽스 - 장면 렌더링) 

* 정렬 후 훨씬 쉬워지는 문제 예시: 이진 탐색 (Binary Search)

• 문제를 더 작은 문제로 쪼개 재귀적으로(recursively) 해결하는 분할정복(Divide & Conquer) 패러다임의 알고리즘
• 배열(array) 에서 특정한 아이템을 찾고자 할 때 사용하는 탐색 알고리즘으로, 배열이 정렬된 상황에서 사용 가능
• 단순히 크기가 n 인 배열 전체를 처음부터 끝까지 스캔하는 방식으로 탐색한다면 선형(linear) 시간 복잡도 O(n) 이 요구되지만, 이진 탐색을 사용할 경우 로그(logarithm) 시간 복잡도 O(log n) 로 해결 가능함
• 입력: 정렬이 완료된 배열 A[0 : n] & 찾고자 하는 아이템 k  -->  출력: k 의 위치 (혹은 존재 여부)
• 오름차순 정렬된 배열 A[0 : n] 에서 아이템 k 를 찾고자 할 때,
  1) 찾고자 하는 k 와 해당 배열의 중간값 A[n/2] 를 비교함
  2-1) if k 가 A[n/2] 보다 작다면, 배열의 앞쪽 절반인 A[0 : n/2] 에 대해 1~2 를 반복함
         - 배열 A 가 이미 정렬되어 있으므로, k 는 뒤쪽 절반인 A[n/2+1 : n] 의 어느 원소보다 작을 것이 자명함
  2-2) elif A[n/2] 보다 k 가 크다면, 배열의 뒤쪽 절반인 A[n/2+1 : n] 에 대해 1~2 를 반복함
  2-3) else A[n/2] 가 곧 찾고자 하던 k 에 해당함. 끝!

* 각각의 정렬 알고리즘들은 저마다의 존재 이유가 있다...!  <-- 입력 값 / 문제의 종류에 따라 가장 빠른 알고리즘이 달라지기 때문

 

 

* 삽입 정렬 (Insertion Sort) 

• 입력: 정렬되지 않은 크기 n 의 배열 A -->  출력: 정렬된 배열 A
• 배열 A 를 구성하는 n 개의 아이템 A[i] (i = 1, 2, ..., n) 에 대해, 이전 단계에서 이미 정렬 완료된 A[0 : i-1] 의 아이템들과 쌍 단위(pairwise) 비교(compare) & 교환(swap) 을 통해 적절한 위치로 삽입하는 방식 (정렬된 i-1 개 아이템 -> 정렬된 i 개 아이템으로 확장!)
• 각 단계(step) 에서 (평균) 비교 & 교환 비용이 O(n/2) * (n-1) 단계 거침  -->  전체 알고리즘 복잡도는 O(n^2)
• #코드 구현 추가 예정!
• [예시 이미지 (n=6)]

 

+ 이진 삽입 정렬 (Binary Insertion Sort)

• 기본적으로 삽입 정렬에서는 아이템 쌍 단위의 비교, 교환에 드는 비용이 동일하다고 가정하고 있음.
• BUT 만약 비교에 드는 비용 >>> 교환 비용인 상황일 경우?!  -->  이진 탐색(Binary Search) 를 활용해서 비교 비용을 줄일 수 있다!
• 각 단계에서 정렬 대상이 되는 아이템 A[i] 은 이미 이전 단계를 통해 정렬 완료된 부분 A[0 : i-1] 과 비교하는 것이므로, 이 때 이진 탐색을 활용하면 O(i) -> O(log i) 로 비교 비용 감소 --> 비교에 드는 총 비용은 O(n log n) 이 됨
• 하지만 이는 교환(swap) 에 드는 비용을 줄여주지는 못하므로 결과적으로 O(n^2) 인 것은 마찬가지...

 

* 병합 정렬 (Merge Sort)

• 이진 탐색과 마찬가지로 분할정복 패러다임의 알고리즘
• 정렬이 필요한 크기 n 인 배열 A 에 대해
  1) 왼쪽 절반 L = A[0 : n/2] / R = 오른쪽 절반 A[n/2 : n] 이 되도록 반으로 쪼갠다. 쪼개진 각각의 요소(배열) 를 다시 반씩 쪼갠다. 이걸 각 배열의 크기가 1이 될 때까지 반복!  -- 분할(Divide) 단계
  2) 가장 말단의 (=크기 1인) 배열부터 다시 한 쌍(pair) 을 만들며 병합해나간다. 이 과정에서 배열 쌍 단위로 아이템의 크기 비교를 하여 점차 정렬된 배열로 합쳐 나가는 것!  --  병합(Merge) 단계
• 병합 연산(Merge operation) 은 이미 (오름차순) 정렬된 & 크기 n/2 인 두 배열 L', R' 가 주어졌을 때, 각 배열의 첫번째 요소부터 요소 쌍 단위로(pairwise) 비교해가며 줄을 세워 (가장 작은 요소부터 오름차순으로) 정렬된 & 크기 n 인 배열 A' 으로 합쳐내는 것  -->  O(n) 의 시간 복잡도를 가짐  
• 분할 단계는 말 그대로 배열을 더 작은 단위로 분할해나가는 것 뿐이고, 실제적인 핵심 연산(operation) 은 병합 단계에서 이루어지기 때문에 '병합 정렬' 이라고 불리는 듯
• #코드 구현 추가 예정!
• 전체 알고리즘의 시간 복잡도는 O(n log n) 이며, 증명은 아래 이미지 참고 :D
• [예시 이미지 (n=7)]

 

 

+ 병합 정렬 대비 삽입 정렬의 장점은?

• 삽입 정렬은 제자리 정렬(in-place sort) 이기 때문에, 정렬 과정에서 O(n) 만큼의 추가적인 공간(auxiliary space) 을 필요로 하지 않음! 
• 다시 말해, 분할 단계에서 기존의 배열 A 의 반쪽인 배열 L, R 과, 병합 단계를 재귀적으로 거쳐 정렬된 배열 A' 을 만들어내는 L', R' 은 다르다. 별도로 저장되어야 한다. 마찬가지로 모든 병합 연산 끝에 얻어진 A' 를 최종적으로 A 에 복사해야 한다는 것! 
• 제자리 정렬(in-place sort) 은 O(1) 상수 시간만큼의 보조 공간을 필요로 할 뿐. 이 때의 보조 공간은 한 쌍(pair) 의 요소를 교환(swap) 하는 과정에서 사용되는 임시 변수에 해당함.
• 반면 병합 정렬은 삽입 정렬 대비 시간 복잡도 면에서 유리함!