[C++] std::sort에 관하여

원래는 막연히 그냥 quickSort를 메인으로 좀 더 개선한 알고리즘으로 정렬한다... 라고만 알고 있었다.

그러다 좀 더 자세한 정보들을 접하게 되면서 글로 남겨본다.

본 글은 아래 링크의 글을 정리한 내용이다.

https://www.geeksforgeeks.org/introsort-cs-sorting-weapon/

Introsort - C++’s Sorting Weapon - GeeksforGeeks

 

현재의 std::sort는 인트로정렬(introSort)를 사용한다.

인트로정렬은 현재 STL에서 기본적으로 제공되는 정렬함수이며, 퀵정렬을 메인으로 하면서 힙정렬,삽입정렬을 추가한 정렬이다.

퀵정렬자체도 물론 시간복잡도 nlogn인 매우 빠른 알고리즘이지만, 최악의 경우(ex.정렬된 배열 + pivot을 최솟값 or 최대값으로 잡은경우) n^2의 시간복잡도를 가지게 된다.

이러한 단점때문에 인트로정렬을 사용한다.

 

인트로정렬의 과정은 아래와 같다.

 

1. 쪼개는 과정에서 리스트의 크기가 16이하라면 이 리스트에 대해서는 '삽입정렬'을 수행한다.

2. 퀵정렬을 수행하는 도중 재귀호출의 깊이가 2*logN을 넘어가게 되면 '힙정렬'로 전환한다.

     여기서 최대깊이 제한을 2*logN으로 정의한다.

3. 즉,   16 < 리스트 크기 < 2*logN 일 경우, 퀵정렬을 수행한다.

 

여기서 16이란값과 2*logN이란 값은 휴리스틱 값이다. 즉, 다양한 테스트 및 연구로 구한 근사치값이다.

 

 

삽입정렬이 사용되는 이유는? (BubbleSort같은것도 있는데?)

-> 참조지역성이 좋다.(연속된 메모리를 비교하기 때문).

-> 어느정도 정렬된 리스트일 경우, 삽입정렬을 사용하면 굉장히 성능이 좋다.

-> 위와 같은 이유들 때문에 작은 배열에 대한 정렬로써는 삽입정렬은 좋은 알고리즘이라고 평가를 받고있다.

 

힙정렬이 사용되는 이유는? (MergeSort같은것도 있는데?)

-> 전적으로 메모리사용량 때문에 그렇다.

    병합정렬(MergeSort)는 O(N)의 공간이 필요하지만, 힙정렬은 O(1)의 공간이 요구된다.