[알고리즘] 인트로 소트 (Intro Sort)

인트로 소트 (Intro Sort)

개념

퀵 정렬의 최악의 경우의 시간복잡도를 보완한 하이브리드 정 알고리즘이다. 힙 정렬, 삽입 정렬 같은 다른 정렬 알고리즘과 결합해 단점을 보완해 효율성을 극대화한다.

원리

정렬 시작: 퀵 정렬을 수행한다.

제한 설정: 재귀 호출 깊이에 임계값을 지정한다 (log n)

정렬 전환: 퀵 정렬이 특정 임계값을 초과하면 힙 정렬로 전환한다.

정렬 전환: 배열의 크기가 작은 경우 삽입 정렬로 전환하여 수행한다.

예시


                    [9, 7, 5, 11, 12, 2, 14, 3, 10, 6] // 피벗: 9
                    
                    [7, 5, 2, 3, 6] [9] [11, 12, 14, 10] // 피벗: 7, 11
//              삽입 정렬 수행             힙 정렬 수행 (재귀가 임계치 넘어갔다 가정)
               [5, 2, 3, 6] [7]   [9]   [10] [11] [12, 14] 
               
               [2, 3, 5, 6] [7]   [9]   [10] [11] [12] [14] // 완료

특징

언제나 O(n log n)의 시간복잡도를 유지하기 때문에 일정하다. 상황에 따라 추가 메모리 사용이 발생할 수 있다. 성능이 보장되고, 범용성이 높아 매우 자주 사용된다.

참고로, std::sort에서 인트로 소트를 사용한다.