[C++] Intro sort 인트로 정렬 C++

C++에서 제공하는 정렬 함수: IntroSort

C++의 알고리즘 헤더에서는 sort() 함수를 지원한다. 정말 많은 sort 알고리즘이 존재하지만 C++에서 제공하는 정렬 함수는 어떤 알고리즘을 사용하는지 알아보자.

정렬 알고리즘의 종류와 시간 복잡도

여러가지 알고리즘에 대한 간략한 설명과 시간 복잡도를 보면 다음과 같다.

알고리즘	시간 복잡도 (최선)	시간 복잡도 (평균)	시간 복잡도 (최악)	공간 복잡도
퀵 정렬 (Quick Sort)	O(n log n)	O(n log n)	O(n²)	O(log n)
힙 정렬 (Heap Sort)	O(n log n)	O(n log n)	O(n log n)	O(1)
삽입 정렬 (Insertion Sort)	O(n)	O(n²)	O(n²)	O(1)

C++의 IntroSort

이런 널리 알려진 정렬 알고리즘과 달리 C++에서는 IntroSort라는 방식을 사용한다. IntroSort는 특별한 새로운 알고리즘을 사용하는 것이 아니라 기존의 정렬 알고리즘들을 짬뽕하여 각각의 장단점을 보완하는 방식이다. 퀵 정렬을 베이스로 삽입 정렬과 힙 정렬을 사용하여 퀵 정렬에서의 최악의 경우를 보완하는 방식이다.

IntroSort의 동작 과정

• 배열의 크기가 16 이하라면 삽입 정렬을 시행한다.
  • 배열의 크기가 작을 때는 삽입 정렬이 퀵정렬보다 빠르기 때문에 이 조건을 사용한다.
• 퀵 정렬을 수행한다.
  • 퀵 정렬을 사용하지만, 깊이가 너무 깊어지면 성능이 떨어지므로 일정 깊이 이상에서는 힙 정렬을 사용한다.
• 힙 정렬을 사용하여 최악의 경우를 보완한다.
  • 퀵 정렬이 최악의 경우 성능이 나빠지지 않도록 힙 정렬을 사용하여 보완한다.

IntroSort 의사코드

int type; // 0 : Asc, 1 : Desc

bool Compare(int a, int b) {
    return type ? a > b : a < b;
}

void Insertion_Sort() {
    for (int i = 1; i < size; i++) {
        int key = arr[i];
        int j = i - 1;
        for (j; j >= 0 && Compare(key , arr[j]); j--) {
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = key;
    }
}

void Heap_Sort(int left, int right) {
    priority_queue<int> pq;
    for (int i = left; i < right; i++) {
        pq.push(arr[i]);
    }
    for (int i = left; i < right; i++) {
        arr[i] = pq.top();
        pq.pop();
    }
}

void Quick_Sort(int left, int right, int depth) {
    if (depth == 0) {
        int size = right - left + 1;
        if (size > 16) Heap_Sort(left, right);
        return;
    }
    int i = left, j = right;
    int pivot = arr[(left + right) / 2];
    int temp;

    do {
        for (; Compare(arr[i] , pivot); i++);
        for (; !Compare(arr[j] , pivot); j--);
        if (i <= j) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++, j--;
        }
    } while (i <= j);

    if (left < j) Quick_Sort(left, j, depth - 1);
    if (i < right) Quick_Sort(i, right, depth - 1);
}

void Sort() {
    if (size <= 16) {
        Insertion_Sort();
        return;
    }
    Quick_Sort(0, size - 1, 2 * ceil(log2(size)));
    Insertion_Sort();
}

결론

IntroSort는 퀵 정렬, 삽입 정렬, 힙 정렬을 결합하여 다양한 크기와 특성을 가진 데이터에서 최적의 성능을 발휘한다. 퀵 정렬의 최악의 경우 성능 저하를 막기 위해 삽입 정렬과 힙 정렬을 결합한 점이 특징이다. C++의 sort() 함수는 IntroSort를 사용하여 대부분의 경우에서 O(n log n) 시간 복잡도를 보장하며, 최악의 경우에도 성능을 안정적으로 유지한다.