[백준] 10814번 나이순 정렬 (C++)

문제

https://www.acmicpc.net/problem/10814

10814번: 나이순 정렬

코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

bool compare(pair<int, string> p1, pair<int, string> p2){
  return p1.first < p2.first;
}

int main(){
  int n;
  vector<pair<int, string>> v;
  cin >> n;

  for(int i=0; i<n; i++){
    int x;
    string y;
    cin >> x >> y;
    v.push_back(make_pair(x, y));
  }

  stable_sort(v.begin(), v.end(), compare);

  for(pair<int, string> p : v){
    cout << p.first << ' ' << p.second << '\n';
  }

  return 0;
}

정리

sort()함수를 사용할 경우 이 문제는 해결이 되지 않는다.

sort()함수 대신 stable_sort()함수를 사용해야 한다.

 

sort()함수 : 퀵정렬 알고리즘으로 구현되어 있다. 퀵 정렬은 순서를 보장할 수 없는 불안정 정렬 알고리즘이다.

stable_sort()함수 : 병합정렬 알고리즘으로 구현되어 있다. 병합정렬은 안정 정렬 알고리즘이다.

 

불안정 정렬(unstable sort) : 중복된 값이 입력 순서와 동일하지 않게 정렬되는 알고리즘

ex) 삽입정렬, 병합정렬, 버블정렬

안정 정렬(stable sort) : 중복된 값이 입력 순서와 동일하게 정렬되는 알고리즘

ex) 퀵정렬, 선택정렬, 계수정렬

 

즉 불안정 정렬을 사용할 경우 나이가 같으면 가입한 순서가 바뀔 우려가 있다. 그래서 안정 정렬을 해주는 stable_sort()함수를 사용해야 이 문제를 해결할 수 있다.

참조

https://jaetsby.tistory.com/16

https://hongl.tistory.com/9