c++) sort와 stable_sort

c++의 sort와 stable_sort의 차이.

 

sort는 불안정정렬이고 

stable_sort는 안정정렬이다.

 

안정정렬은 동일한 값이 있을때 기존의 순서가 유지되는 정렬이며,

불안정정렬은 그렇지 못한 정렬이다. 

 

 

다음과 같이 벡터가 선언되었고

vector<pair<int,int>> v = {{1,2}, {2,3}, {1,4}};

pair의 첫번째 요소를 기준으로 정렬을 한다고 하면 

 

불안정정렬인 sort 함수를 사용하면 

{1,2}, {1,4}, {2,3} 으로 정렬될수도있고

{1,4}, {1,2}, {2,3}으로 정렬될수도 있다. 

 

하지만 안정정렬인 stabe_sort 함수를 사용하면 무조건 원래 앞에 위치해 있던 {1,2}가 앞으로 오는것이 보장된다.

{1,2}, {1,4}, {2,3}

 

 

stable_sort를 사용해야하는 문제:

https://tose33.tistory.com/403

프로그래머스. 파일명 정렬