(C++)Sort/Stable_sort

대표적인 정렬함수 중에서

#include<algorithm>

헤더를 추가하면 사용할 수 있는 sort()는 정렬 알고리즘뿐만 아니라 많이 사용되고 있다.

오늘은 간단하게 sort와 stable_sort를 알아보도록하자.

1. sort

#include<algorithm>	//헤더 추가

vector<string>vec;
int main()
{
   int n;
   string input;
   cin >> n;

   for (int i = 0; i < n; i++)
   {
      cin >> input;
      vec.push_back(input);
   }

   sort(vec.begin(), vec.end());

   for(int i = 0; i < vec.size(); i++)
   {
      cout << vec[i] << " ";
   }

}

input에 100 1 10000 1000 10 순으로 입력을 했다고 가정하자.
sort()를 거치면 자동으로 오름차순으로 정렬 (1 10 100 1000 10000)

내림차순을 하고싶다면 전에 정리한 글이 있으니 참고하면된다.

2. stable_sort

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
vector<pair<int, string>>vec;

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

int main()
{
   int n;
   cin >> n;

   for (int i = 0; i < n; i++)
   {
      int age;
      string name;
      cin >> age >> name;
      vec.push_back(make_pair(age, name));
   }

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

   for (int i = 0; i < n; i++)
   {
      cout << vec[i].first << " " << vec[i].second << '\n';
   }

   return 0;
}

age와 name 두 변수에 원하는 데이터들을 집어넣었다고 가정하자.
동명이인 혹은 동갑일 수 있는데 이럴때 어떻게 정렬이 되는지?
뒤에 이름은 사전순으로 정렬이 될 것이다.

ex)
 vec.push_back(make_pair(20, bbb));
 vec.push_back(make_pair(20, aaa));
 vec.push_back(make_pair(22, ccc));
 vec.push_back(make_pair(25, ddd));

로 집어 넣는다면 bbb가 aaa보다 사전기준 큰 값이기 때문에 aaa가 첫번째 원소로 정렬이 된다.

이러한 현상을 극복하기 위해 stable_sort()를 사용한다.

물론 sort()할 때 compare를 선언 후 사용해주면 되지만 불안정하다.

즉 stable_sort()를 사용하면 같은 값일 때 확정적으로 순서대로 정렬이 되기 때문에 안심하고 사용해도 된다.

(추가)stable_sort를 사용할 때에는 compare 함수를 꼭 선언해줘야한다!!!

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