퀵 정렬은 참 미묘하고도 재밌는 정렬 방법입니다. 일단 퀵 정렬은 일반적인 조건에서 가장 성능이 좋은 정렬 알고리즘 중 하나입니다. 그래서 C나 C++ 언어의 표준 라이브러리에서는 퀵 정렬 혹은 퀵 정렬을 개선한 하이브리드 알고리즘을 사용합니다. (Java의 경우는 개선된 병합정렬을 사용합니다)퀵 정렬은 분할을 재귀적으로 수행하는 알고리즘입니다. 그래서 보통의 경우에는 Divide and Conquer 알고리즘이 보여주는 O(NlogN) 성능을 나타내지만 경우에 따라 O(N*N)의 성능이 나오기도 하는 등 변덕스럽기 그지 없습니다.
퀵 정렬 자체는 단순하고 아름답지만, 이런 최악의 성능을 보이는 경우를 피하기 위해 여러가지 회피 방법이 연구되었습니다. 어떤 식으로 이런 문제를 해결하는지 살펴보는 것도, 자신에게 닥친 문제를 어떻게 해결하는지에 대한 좋은 사례가 됩니다.
많이 사용되는 알고리즘이면서도 배울게 많은 알고리즘이라 퀵 정렬에 대해서는 반드시 꼼꼼하게 익혀두는 것이 좋겠습니다.
강의 자료
강의 동영상
10.0 퀵정렬 - 시작 : 퀵정렬은 현실 세계에서 가장 많이 사용되는 실용적인 알고리즘입니다. 퀵정렬의 기본 원리와 그의 개선을 통해 얼마나 성능이 향상되는지를 보면 매우 흥미롭습니다.
10.1 퀵정렬 개요 : 퀵정렬은 분할(Partition)을 재귀적으로 수행하여 정렬을 합니다. 분할이 무엇인지 그리고 퀵정렬은 어떻게 정의될 수 있는지 알아봅니다.
10.2 퀵정렬의 구현 : 기본적인 퀵정렬을 재귀적인 방법으로 구현해 봅니다. 재귀호출의 단점을 개선하기 위해 스택을 사용하여 재귀호출을 제거한 버전도 구현해 봅니다.
10.3 퀵정렬의 분석 : 퀵정렬의 성능은 변덕이 심합니다. 최선의 경우와 최악의 경우, 극단적인 성능 차이를 보여주는데... 어떤 조건에서 그런지 알아야 문제를 해결할 수 있습니다.
10.4 퀵정렬의 개선 : 퀵정렬의 성능이 변덕스러운 점을 개선하기 위해서는 분할이 잘 되어야 합니다. 난수와 Media-of-Three 기법을 이용하여 분할이 극단적이 되지 않도록 할 수 있습니다. 또한 작은 구간에 삽입정렬을 이용하면 재귀호출의 깊이를 줄일 수 있습니다.
10.5 qsort : C 표준 라이브러리에는 일반적인 타입에 대해 적용할 수 있는 퀵정렬 알고리즘인 qsort라는 API를 제공합니다. qsort를 사용하는 방법을 알아봅니다.
10.6 퀵정렬의 성능 비교 : 지금까지 알아 본 퀵정렬과 그의 개선 버전들에 대해 실제로 돌려보면서 성능을 분석해 봅니다.
10.7 Selection 문제 : 퀵정렬의 기본 동작인 분할을 이용하면 집합에서 10번째 큰 값이 무엇인가?와 같은 Selection 문제를 효율적으로 해결할 수 있습니다. 그 방법에 대해 구체적으로 알아봅니다.
10.9 퀵정렬 - 결론 : 퀵정렬은 기본 구현도 재미있고, 그 개선도 흥미로운 알고리즘입니다. 이번 장에서 배운 내용들을 정리해 봅니다.
관련글 |
- C++로 배우는 알고리즘
- 9장 : 정렬의 기본
- 11장 : 힙 정렬
댓글 없음:
댓글 쓰기