[C++] stable_sort

알아두면 유용할 것 같아서 정리

 

C++ 에서 pair를 이용하면 두가지 데이터를 하나의 pair에 저장할 수 있다.

문제를 풀 때, 첫번째 요소는 오름차순으로 정렬을 하고 첫번째 요소가 같은 경우에 두번째 요소는 입력한 그대로 = 즉 두번째 요소는 건드리지 않고 정렬을 하라고 했을 때 어떻게 할까?

 

난 cmp함수를 만들어서 #include<algorithm>안에 있는 sort함수를 써서 첫번째 요소만 정렬을 했다! 그러면 되는줄..

 

그런데 정렬하는 함수에는 불안정한 정렬인 sort와 안정한 정렬인 stable_sort가 있었다.

무슨 뜻인고 하니, 불안정한 정렬인 sort는 위의 경우에서 두번째 요소에 대해 언급이 없을 때, 두번째 요소가 변하지 않는다는 보장이 없다!

안정한 정렬인 stable_sort는 두번째 요소를 건드리지 않고 정렬을 하게된다. 즉, 입력한 그대로가 유지되는 것이다.

 

왜 이런 차이가 발생할까?

sort는 퀵정렬이고 stable_sort는 합병정렬이기 때문이다.

합병정렬은 merge sort라고도 하는 분할 정복을 사용하는 정렬!

나는 합병정렬이라고 배웠는데 인터넷으로 찾아보니 병합정렬이라고 하시는 분들이 많다.

합병 = 병합 = merge 같은 것

 

여담으로 퀵정렬은 O(log n) 이고 합병정렬은 O(n log n)이다.

 

 

 

 

 

 

 

 

[C++] 백준 알고리즘 10814 나이순 정렬 (tistory.com)

[C++] 백준 알고리즘 10814 나이순 정렬