인트로 정렬(intro sort)에서 삽입정렬(insertion sort) 과 퀵소트(quick sort)의 상관 관계

사실 인트로 정렬에서 핵심 되는 부분은 재귀 깊이에 따라 힙소트로 넘어가는 부분이다. 하지만 인트로 정렬에서 어떤 기준으로 insertion sort를 할지 quick sort를 할지에 대한 궁금증이 생겨 인트로 정렬(intro sort)에서 삽입정렬(insertion sort)과 퀵소트(quick sort)의 상관관계에 대한 글을 작성했다.

본 글은 재미를 위한 글입니다. 어떠한 검증도 받지 않았으므로 많은 오류가 포함되어 있을 수 있습니다.

인트로 정렬이란

quick sort는 이름 그대로 빠른 정렬을 가능하게 해준다. 하지만 특정 조건에서 O(n^2)으로 매우 느려지는데, 이를 극복하고자 나온 것이 인트로 정렬이다. 의사코드는 다음과 같다.


procedure sort(A : array):
    let maxdepth = ⌊log2(length(A))⌋ × 2
    introsort(A, maxdepth)

procedure introsort(A, maxdepth):
    n ← length(A)
    if n < 16:
        insertionsort(A)
    else if maxdepth = 0:
        heapsort(A)
    else:
        p ← partition(A)  // assume this function does pivot selection, p is the final position of the pivot
        introsort(A[1:p-1], maxdepth - 1)
        introsort(A[p+1:n], maxdepth - 1)
//출처: https://en.wikipedia.org/wiki/Introsort

길이가 16 미만이라면 -> insertion sort

깊이가 제한 조건에 도달하면 (=quick sort 최악의 상황에 해당하면) -> heap sort

else ->

피봇 선택

재귀 호출(quick sort)

여기서 평균적으로 O(n long n)이 보장되는 quick sort를 계속 사용하지 않고 O(n^2)인 insertion sort를 사용하는 이유는 n이 충분히 작으면 상수가 작은 O(N^2) 알고리즘이 상수가 큰 O(n log n) 알고리즘보다 빨리 작동하기 때문이다.

인트로 정렬에서 삽입정렬과 퀵소트의 상관 관계

gcc나 여러 의사코드 등 대부분의 문헌은 16을 기준으로 하고 있었다. 그래서 16이라는 숫자가 유도되는 과정이 궁금해 관련 근거를 찾아봤다. 그러나 기대와는 다르게 16이라는 기준에 대한 설명은 다양한 테스트와 연구로 인한 경험적 근사치라는 설명이 전부였다. 많은 자료에서 사용하고 있는 숫자가 경험적 근사치라는 게 믿기지 않았고, 컴파일러별 intro sort 구현을 직접 찾아보기로 하였다.

gcc : 16(배열의 길이)

llvm : __limit 값의 기본값 -> 6 만약, is_trivially_copy_constructible인 경우(복사 비용이 저렴한 경우) 30

vc++ : 32(배열의 길이)

구현 별로 기준값이 다름을 알 수 있다. 이와 함께 다음과 같은 사실을 생각해 볼 수 있는데,

big O notation은 상한선만을 따진다

정렬에서의 big O notation은 비교 횟수를 의미하지 절대적인 속도를 의미하지 않는다.

n에 따라서 O(n log n) 알고리즘보다 상수가 작은 O(N^2) 알고리즘이 더 빠를 수 있다.

결론

결국 많은 문헌에서 사용되던 16이라는 숫자는 특정 과정을 통해 계산된 숫자라기보다는 시스템에 따라 달라질 수 있는값이라고 보는 게 적절했다.

느낀 점

big O notation은 알고리즘의 속도를 결정짓는 여러 요소 중 하나일 뿐이며, big O notation에서 생략되는 상수들도 마냥 무시할 수는 없다는 것을 다시 한번 깨달을 수 있었다 stack overflow에서 성능을 묻는 글에 직접 실행해 봐야 알겠지만…. 이라는 내용을 당연하게 여기고 넘어간 나 자신에 대해 반성하며, 이 시간에도 모두를 위해 프로그램의 성능을 측정하고 있을 누군가에게 존경을 바친다. ~~풍동 실험~~