[C++] stable_sort

헤더파일 및 사용방법

 

헤더파일 : <algorithm>

 

stable_sort(시작점주소, 마지막점주소 +1, 함수);

#include <iostream>
#include <algorithm>

int main(){
    int arr[6] = {2,4,3,5,2,1};
    
    stable_sort(0, 5+1);
    
    for(int i = 0; i < 6; i++){
        cout<< arr[i];
    }	// 1 2 2 3 4 5
}

 

 

sort VS stable_sort

 

1. 기능적인 차이

먼저 sort를 간단하게 정리하자면, <algorithm> 헤더파일을 선언하여 오름차순으로 정렬하는 함수이다.

sort(시작점주소, 마지막점주소 +1, 함수); 형태로 사용하며, 세번째 인자 함수의 반환값에 맞게 정렬이 동작한다. (없으면 단순 오름차순 정렬) 

그런데, sort는 동일한 값의 요소들에 대해, 두 요소가 기존에 가지고 있던 순서를 보장하지 않는다.

 

그러나, stable_sort()는 동일한 값의 요소들에 대해, 두 요소가 기존에 가지고 있던 순서를 보장한다.

 

따라서, 위 예제에서 2가 중복해서 나왔다고 하더라도 첫번째 2는 정렬 전 arr[0]의 2이고, 두번째 2는 정렬 전 arr[4]의 2이다.

 

2. 시간복잡도 측면의 차이

시간복잡도의 측면에서는 퀵정렬로 정렬을 처리하는 sort()가 병합정렬(merge sort)로 정렬을 처리하는 stable_sort()보다 빠르다.
>> sort(): 평균적으로 약 O(Nlog₂(N))의 요소 비교와 최대 요소 개수만큼의 값 교환(또는 이동)을 수행한다 (N은 first와 last의 거리를 뜻한다).
>> stable_sort(): 충분한 메모리가 있다면 약 O(Nlog₂(N)), 충분한 메모리가 보장되지 않는다면 약 O(Nlog₂²(N)) 시간만큼의 요소 비교와 최대 요소 개수만큼의 값 교화을 수행한다. (N은 first와 last의 거리를 뜻한다)

참고>> https://developer-b.tistory.com/22

 

2-1. stable_sort는 예측할 수 있는 안정적인 정렬이므로, sort보다 빠르며 더 유용하게 쓰인다.

 

 

 

 

참고>>

https://developer-b.tistory.com/22

https://codingwell.tistory.com/44