sort / stable_sort

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool compare(pair<int,int> a, pair<int,int> b) {
	return a.first < b.first;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	vector<pair<int, int> > v, v2;
	v.push_back(make_pair(1,2));
	v.push_back(make_pair(4,4));
	v.push_back(make_pair(4,2));
	v.push_back(make_pair(3,2));
	v.push_back(make_pair(5,2));
	v.push_back(make_pair(7,4));
	v.push_back(make_pair(9,7));
	
	v2 = v; 
	
	cout << "<Before Sorting>";
	for(auto i : v) {
		cout << "(" << i.first << "," << i.second << ") ";
	}
	cout << '\n';
	
	sort(v.begin(), v.end(), compare);
	cout << "<After Sorting>";
	for(auto i : v) {
		cout << "(" << i.first << "," << i.second << ") ";
	}
	cout << '\n' << '\n';
	
	
	cout << "<Before Stable_Sorting>";
	for(auto i : v2) {
		cout << "(" << i.first << "," << i.second << ") ";
	}
	cout << '\n';
	
	stable_sort(v2.begin(), v2.end(), compare);
	cout << "<After Stable_Sorting>";
	for(auto i : v2) {
		cout << "(" << i.first << "," << i.second << ") ";
	}
	
	return 0;
}

---

위에서 sort와 stable_sort의 결과는 어떨까?

물론 결과는 같게 나온다.

 

하지만 구분되어 있는 이유는 뭘까?

이것이 다른점은 위 코드에서 (4,4)와 (4,2)를 정렬할 때 발생한다.

 

위에서 sort와 stable_sort의 정렬기준은 compare 함수를 기준으로 정렬을 하게 되는데,

첫번째 값만 비교해서 정렬을 하게 된다.

 

따라서 (4,4)와 (4,2)는 같은 값이나 다름없게 비교된다.

 

이런 값에 대해 sort는 어떤 값이 앞에 와야 하는지 불확실하다.

한마디로 "등가 요소의 상대적 위치가 보증되지 않는다." 이다.

 

stable_sort는 원래 앞에 있던 값이 계속 앞에 있게 된다.

한마디로 "등가 요소의 상대적 위치가 보증된다." 이다.