알고리즘 공부는 마치 벽을 넘는 것과 같다.
이해하지 못하면 정말 답답하지만 원리를 알고 나면 고개를 끄덕이게 된다. 물론 이해한다는 것이 구현할 수 있다는 것을 뜻하지는 않지만, 알고리즘 공부에서 가장 중요한 것은 원리를 알고 있느냐는 것이다.
특히 정렬 알고리즘의 구현 과정은 단순하면서도 논리적으로 매우 정밀한 부분들이 복합적으로 조직화 되는 과정이므로 통 암기를 하면 모를까, 이해->구현으로 과는 과정은 오랜 경험이 필요하다.
병합정렬(merge sort) vs 퀵정렬(quick sort)
2014/11/24 - [프로그래밍/알고리즘] - 퀵정렬 알고리즘(Quick sort)
병합정렬은 퀵정렬(quick sort)과 마찬가지로 분할점령의 방법을 쓴다. 분할 점령은 원래의 문제를 같은 형식의 두 개 이상의 문제로 나누어 따로따로 생각하여 재귀적인 방법으로 해결하는 방법을 말한다. 퀵정렬과 마찬가지로 O(nlogn)의 시간복잡도를 가지는데, 퀵정렬의 경우는 최악의 경우 O(n2)의 시간복잡도를 가지지만 병합정렬의 경우는 항상 O(nlogn)의 시간복잡도를 가지므로 퀵정렬 보다 빠를거라 생각 될 수 있다. 하지만 실제 사용에서는 퀵정렬의 성능이 20%더 좋다는 것이 일반적이다.(이 부분은 필자가 확실히 계산한 것은 아니니 자세한 내용은 따로 찾아보길 바란다.) 사실 퀵정렬의 경우 O(n2)의 시간복잡도를 가지기 위해서는 오름차순 또는, 내림차순으로 정렬된 자료집합이어야 한다. 이렇게 랜덤하게 주어진 자료가 오름차순 또는 내림차순으로 제공될 확률을 계산해보면 2/n!이어야 하고 자료의 크기가 10개정도만 되어도 이런 식으로 자료가 주어질 확률은 거의 불가능에 가깝게 된다.
병합정렬의 시간복잡도
logn의 의미
병합정렬의 시간복잡도는 O(n×logn)이다. 위 그림을 보면 자료의 크기를 완전 분해하기 까지 logn개의 호출레벨이 생긴다는 것을 알 수 있다. 자료의 수가 9개 따라서 23 < 호출레벨 <=24가 된다. 만약 자료의 수가 64개라면 log64 = 6가 되고, 호출 레벨이 6이 된다.
n의 의미
n의 의미는 병합을 하는 알고리즘에 있다. 병합하는 알고리즘은 각각의 나누어진 경우에서 각 원소들을 비교하여 새로운 버퍼에 하나씩 집어넣는다. 버퍼의 크기 만큼 비교가 일어나고 버퍼의 크기는 원래의 자료의 크기이므로 n번 이루어진다.
따라서 시간 복잡도는 O(n×logn)이 된다.
병합하는 과정
병합하는 과정은 분해과정의 역순이라고 생각하면 된다. 왜냐면 재귀가 회귀할 때 일어나는 일이므로 그렇다.
비교하여 순서대로 임시 버퍼에 집어 넣은 후 위 그림처럼 원래의 자료형으로 복사를 한다. 처음 분할과정의 역순이지만 자료들이 순서대로 정렬되는 것을 알 수 있다.
병합정렬은 퀵정렬과 같은 분할 정렬이지만 약간의 차이가 있다. 퀵정렬은 각 분할과정마다 반드시 하나의 요소의 위치를 결정하지만, 병합정렬의 경우는 분할이 모두 끝난 뒤 정렬을 시작한다는 점이 다르다. 분할 기준도 병합정렬은 자료를 분해할 때 자료를 반으로 쪼개지만, 퀵 정렬의 경우는 분할하는 방법이 자료에 따라서 달라진다. 쪼개는 방법에 따라서 성능의 차이가 날 수 있기 때문에 최악의 경우 시간복잡도가 O(n2)이 되기도 하는 것이다.
다음은 병합정렬의 간단한 소스다.
다음 사이트는 여러 알고리즘을 간단히 비교한 사이트다.
http://www.sorting-algorithms.com/
알고리즘 공부는 매력적이지만, 때로는 인내심을 요구한다.