이 장에서는 두가지의 실용적인 정렬 알고리즘을 소개 드립니다. 하나는 쉘 정렬(Shell Sort)로서 활용도가 높은 삽입 정렬의 성능을 대폭 개선한 것입니다. 삽입 정렬의 장점을 하나도 버리지 않고 장점만 추가된 멋쟁이 알고리즘입니다. 개선의 핵심은 새로 추가된 요소가 들어갈 자리를 순차적으로 비교하지 않고 듬성듬성 건너뛰어 비교하며 찾아낸다는 점입니다. 삽입정렬이 비교횟수에 비해 교환횟수가 지나치게 많았던 단점을 획기적으로 개선한 알고리즘입니다. 단순한 알고리즘이라 구현도 쉽고, 오버헤드도 거의 없습니다.
병합 정렬(Merge Sort)은 직관적인 정렬 알고리즘으로 두개의 정렬된 단위(run)를 순차적으로 끄집어내어 새롭게 큰 단위로 옮기는 방법을 재귀적으로 수행합니다. 쉽게 말해 아이들을 두 그룹으로 나눈뒤에 각 그룹에서 키대로 배열하여 각 그룹의 앞에 키가 작은 아이들이 오게 합니다. 그러고 나서 각 그룹의 제일 앞 아이들을 비교하여 키가 작은 아이를 뽑아 새로운 그룹으로 넣는 방식입니다.
병합정렬은 O(NlogN) 성능을 보이는 알고리즘 중 거의 유일하게 안정적(Stable)인 알고리즘입니다. 요란스럽게 앞뒤로 교환을 하지 않는다는 뜻이죠. 이러한 특성으로 순차적 접근의 효율성이 랜덤 접근보다 더 높은 하드디스크 같은 곳에서 유용한 알고리즘입니다. 대규모의 데이터들은 메모리 보다는 하드디스크에 저장되어 처리되어야 하는데, 순차적 접근만을 사용하는 병합 정렬은 이렇게 외부 매체에 담긴 데이터를 정렬하는데 유리합니다. 다만 병합정렬은 별도의 메모리 공간이 필요로 한다는 단점이 있습니다.
이렇게 쉘 정렬은 단순하면서도 높은 성능 때문에, 병합 정렬은 성능 좋고 안정적이면서 순차 접근법을 쓴다는 점 때문에 실제 현업에서 많이 쓰이는 알고리즘들입니다. 특히 쉘 정렬의 성능은 실제로 돌려보면 깜짝 놀랄 정도로 매우 좋습니다.
그래서 이 두 정렬 방법은 꼭 익혀두어야 합니다.
강의 자료
강의 동영상
12.0 쉘 정렬, 병합 정렬 - 시작 : 이번 장에서는 비교적 직관적이고 쓰임새 많은 쉘 정렬과 병합 정렬에 대해 배워봅니다.
12.1 쉘 정렬의 개념 : 쉘정렬은 교환 횟수가 많은 삽입정렬의 단점을 개선한 알고리즘입니다. 어떤 식으로 교환 횟수를 줄일 수 있는지 알아봅니다.
12.2 쉘 정렬의 구현 : 앞서 배운 쉘정렬의 개념을 코드로 구현해 봅니다. 교환 대상을 정하는 수열을 최적화하여 성능을 개선하는 방법도 알아봅니다.
12.3 쉘 정렬의 분석 : 쉘정렬은 고무밴드가 조여지는 이상적인 모양을 보여줍니다. 이론적으로 O(N*N) 알고리즘과 유사하지만 실제로는 오버헤드가 적어 훨씬 더 좋은 성능을 보여줍니다. 쉘정렬을 여러모로 분석해 봅니다.
12.4 병합 정렬의 개념 : 병합정렬은 매우 직관적인 정렬 알고리즘입니다. 이해하기 쉽고 구현하기 쉽고 성능까지 좋습니다. 병합정렬의 개념에 대해 알아봅니다.
12.5 병합 정렬의 구현 : 병합정렬은 이해하고 구현하기 쉽고 성능 좋은 알고리즘이지만 데이터 집합 크기 만큼의 부가 메모리를 필요로 합니다. 그리고 메모리 복사도 빈번히 일어납니다. 실제로 병합정렬을 구현해보고 성능을 개선해 봅니다.
12.6 병합 정렬의 분석 : 병합정렬의 성능을 분석해 봅니다. 병합정렬은 속도는 빠르지만 메모리를 많이 사용합니다.
12.7 쉘 정렬, 병합 정렬 성능 분석 : 이 장에서 배운 쉘정렬과 병합정렬 그리고 그의 개선 버전들에 대해 실제로 돌려보아 성능을 비교해 봅니다. 쉘정렬이 병합정렬 못지 않게 성능이 좋다는데에 아마 놀라게 될 겁니다.
12.9 쉘 정렬, 병합 정렬 - 결론 : 이번 장에서 배운 쉘정렬과 병합정렬은 쓰임새가 많습니다. 쉘정렬은 간단한 코드에 성능이 매우 좋다는 점에서, 병합정렬은 안정적이며 외부 정렬에 강하다는 점에서 실무에서 많이 쓰입니다. 배운 내용들을 정리해 봅니다.
관련글 |
- C++로 배우는 알고리즘
- 11장 : 힙 정렬 (Heap Sort)
- 13장 : 기수 정렬 (Radix Sort)
댓글 없음:
댓글 쓰기