STL에 구현된 sort()와 stable_sort()을 알아보기 전에 간략하게 sort의 종류와 시간복잡도에 대해서 설명을 해보도록 하겠다.
sort 알고리즘에는 insertion sort, bubble sort, quick sort,... 등 다양한 종류가 있다.
일반적으로 sort 알고리즘을 구분하면 아래와 같이 시간복잡도로 구분을 할 수 있다.
O(n^2): insertion sort, bubble sort, selection sort, ...
O(nlogn): quick sort, merge sort ...
O(n): radix sort, bucket sort, counting sort ...
보통 O(n)의 sort알고리즘의 경우 대부분 특정문제에만 적용이 가능하기 때문에, 일반적으로 sort알고리즘을 이야기하는 경우에는 O(nlogn) 알고리즘인 quick sort나 merge sort가 가장 성능이 좋다고 이야기를 한다.
그럼 O(n^2)의 알고리즘에 비해서 O(nlogn)알고리즘은 얼마나 성능이 좋은 것일까??
간단하게 아래와 같이 산술적으로 계산을 해보면, 두 시간복잡도 사이에 성능차가 얼마나 큰지 직관적으로 알 수 있다.
무작위로 값이 저장된 1,000,000 개의 배열을 정렬한다고 가장해보자
이 경우, 정렬하는데 걸리는 시간은 아래와 같다고 이야기 할 수 있다. (단위는 간략하게 초로 지정)
O(n^2)알고리즘 소요시간: 1,000,000 * 1,000,000 = 1,000,000,000,000초
O(nlogn)알고리즘 소요시간: 1,000,000 * log(1,000,000)= 1,000,000 * 24 = 24,000,000초
결과를 보면 두 알고리즘간의 시간차가 엄청나다는 것을 알 수 있다.
당연히 O(nlogn)알고리즘이 O(n^2)알고리즘보다는 굉장히 빠르며, STL에서도 sorting algorithm을 O(nlogn)알고리즘을 사용하여서 구현하였다.
STL에서는 sort(), stable_sort()라는 두가지 방식을 제공하는데, sort()의 경우에는 quick sort, stable_sort의 경우에는 merge sort로 내부구현이 되어있다. (VS 6.0 기준)
둘다 O(nlogn) 알고리즘인데, 대부분의 STL 책을 보면 대부분의 경우 sort()가 성능이 좋다고 나와있는데, 어떤 기준에 의해서 quick sort로 구현된 sort()의 성능이 좋다고 이야기를 하는 것일까??
사실 수학적인 이론으로 보면, merge sort가 quick sort보다 성능이 더 좋아야 한다.
그런데 어째서, 성능상으로는 quick sort가 더 좋은 성능을 내는 것일까??
그것은 실제 알고리즘의 구현이란 것은, 컴퓨터라는 하드웨어에서 돌아가기 때문이다.
컴퓨터에서 정렬의 대상이 되는 컨테이너는 특정 메모리블럭에 담겨있을 것이다. merge sort의 경우에는 컨테이너의 메모리블럭외에도 정렬을 위한 별도의 추가적인 메모리블럭이 더 필요하다.
이는 별도의 추가적인 메모리생성 및 삭제가 필요하다는 의미일 뿐만 아니라, 컨테이너 메모리블록과 임시메모리블록간의 메모리카피연산이 필요하며 이는 수행시간의 증가를 의미한다.
수학적인 이론적인 개념에서는 메모리생성/삭제/복사 연산의 수행시간이라는 것이 존재하지 않기 때문에, merge sort가 더 효율적이나, 현실의 컴퓨터라는 하드웨어에서 그것이 구현될 경우에는 현실적인 제약(메모리복사..)들에 의해서 quick sort가 더 효율적으로 변하게 된다.
이론적으로 정의된 quick sort, merge sort의 의사코드는 굉장히 심플하고, 멋있다!.
그런데 실제 VS6.0이나 2008에 구현된 코드를 보면 굉장히 복잡함을 알 수 있다.
복잡한 이유는 바로 현실적인 제약 때문이다!!.
그럼 현실적인 제약의 관점에서 sort(), stable_sort() 구현부를 조금씩 살펴보도록 하겠다.
아래는 VS2008에 구현된 stable_sort의 내부구현의 일부이다.
우선 관심을 가질만한 사항은 (1)번으로 표기한 내용이다.
앞에서 stable_sort는 merge sort로 구현이 되어있다고 말했는데, 코드의 내용을 보니, insertion sort를 사용하는 코드가 들어 있다. 이것 역시 현실적인 제약과 관련이 있다.
이론적으로는 O(nlogn)알고리즘인 merge sort가 O(n^2)인 insertion sort보다는 당연히 빠르다.
그러나 현실에서는 적은 수의 원소를 가진 컨테이너의 정렬에는 insertion sort가 가장 빠른것으로 간주한다.
여기서 적은 수란 많은 테스트에 의해서 나온 휴리스틱한 값으로 VS2008에서는 32 (_ISORT_MAX) 로 정의 되어 있다. (내가 예전에 수업에서 들었을때는 16정도였으며, VS6.0에는 16으로 정의되어 있다.)
insertion sort가 작은 컨테이너를 정렬하는데 좀더 빠른 현실적인 이유는 바로 재귀호출의 비용에 있다. O(nlogn)알고리즘은 기본적으로 재귀호출을 이용하여서 구현이 되는데, 이때 발생하는 재귀호출의 비용이 작은컨테이너에서는 상대적으로 크기 때문에, insertion sort가 빠른 경우가 발생하는 것이다.
그래서 좀더 효율적인 sort알고리즘을 만들고자 할 경우에는, 상황에 따라서 다른 알고리즘을 적절히 혼합해서 사용하게 된다.
STL의 stable_sort의 경우에도 큰 단위일때는 merge sort를 사용하다가, 작은 단위로 쪼개지면 insertion sort를 사용하여서 좀더 빠른 효율을 얻고자 한것이다.
다음으로 관심을 가질만한 사항인 (2)항목을 보자.
함수를 보면, _tempbuf 를 계속 인자로 던져주는 것을 볼 수 있다.
위에서 언급한 내용중에 merge sort는 추가적인 메모리블록을 사용하여서 sort를 한다고 하였다.
코드상으로 보면, STL에서는 sort가 시작하는 시점에 _tempbuf를 추가적인 메모리블록으로 할당하여서, 해당 메모리블록을 계속 재사용하고 있음을 알 수 있다. 이로써 얻게 되는 장점은 메모리 생성/삭제를 1번만 한다는 것이다.
만약 재귀함수내에서 필요한 순간마다 메모리블록을 생성/삭제를 한다면, 생성/삭제 비용에 의해서 수행시간은 꽤 느려졌을 것 이다.
우선 sort() 구현에 사용되는 알고리즘이 quick sort에서 quick sort와 heap sort를 혼합한 intro sort 로 변경되었다는 점이 흥미롭다.(실제로 vs6.0 에서는 quick sort로 구현되어 있으나, vs2008에서는 intro sort로 구현되어 있음)
intro sort의 주요 특징은 기본적으로 quick sort와 동일하게 동작하나, 재귀호출의 깊이가 어느정도 깊어지면, 쪼개진 문제를 heap sort를 사용하여서 정렬한다는 점이다.
아래에 표시된 (1)항목을 보면, 재귀호출의 깊이가 1.5log2(N)보다 깊어지면 heap sort를 사용하여서 정렬하는 내용을 확인 할 수 있다.
sort는 우리가 자주 사용하고 있으며, 가장 기본적인 기능 중에 하나일 것이다. 이런 기본적인 sort 하나에도 다양한 개념들이 들어있다는 사실은 굉장히 흥미로운 부분이 아닐 수 없다.
지금까지 STL에 구현된 sort에 대해서 간략하게 기술하였다.
sort 같은 기본적인 개념도 내부구현을 보면 꽤 복잡하게 되어 있다. 어째서 이렇게 복잡하게 구현이 되었는가에 대한 이유를 모른다면, 소스를 쫓아가기가 무척 힘들었을 정도이다.
모든 사물을 이해하려면, 어째서 그 물체가 그런 모양을 가지게 되었는지 근본원리나 원인에 대해서 우선 알게되면, 자연히 이해가 빨라진다.
그래서 이번 포스팅에서는 우선 sort의 종류와 시간복잡도에 대해서 간략하게 설명하고, 그후에 현실적인 제약에 의해서 변형된 sort의 효율성에 대해서 설명한 후에, STL에서 구현된 sort에서 관심가는 부분만 나열해 보았다.