[C++/STL] algorithm헤더의 sort함수

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

1181번: 단어 정렬

백준 문제 1181번 : 단어정렬 문제를 풀다가 sort STL에 대해서 공부하게 되었다.

 

기본적으로 algorithm 헤더에 있는 정렬 함수는 여러가지가 있는데, 기본적인 sort와 stable_sort의 특징은 이렇다.

-std::sort(begin, end, compare)
기본적으로 quick sort로 구현, 재귀가 깊어지면 heap_sort를 사용.
복잡도 : 평균 (N log N)
불안정정렬

-std::stable_sort(begin, end, compare)
기본적으로 merge sort로 구현
복잡도 : 평균 (N log N) // 메모리 양이 부족하다면 최악의 경우 O((N log N)2)
안정정렬 (stable)

 

우선 기본적으로 sort가 stable_sort보다 빠르다.

하지만 sort 함수는 불안정정렬을 수행하고, stable_sort 함수는 안정정렬을 수행한다.

이 뜻은 무엇이냐면, sort 함수는 기본적으로 매개변수 comp의 조건에 따라 정렬을 수행하게 된다.

하지만 sort함수는 qucik sort로 구현되어 동일한 조건에 대해서 불안정한 정렬이기 때문에 정렬된 값이 항상 일정하지 못하고 순서가 변하게 될 수 있다.

하지만 stable_sort는 merge sort로 구현되어 안정정렬이기 때문에 동일한 조건의 경우 기존의 순서를 유지하여 정렬해주게 된다.

 

백준 1181번 문제를 예로 들면 이렇다.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string str[20000];
bool compare1(string s1, string s2)
{
	return s1 < s2;
}
bool compare2(string s1, string s2)
{
	return s1.length() < s2.length();
}
int main()
{
	int num;
	cin >> num;
	for (int i = 0; i < num; i++)
		cin >> str[i];
	sort(str, str + num, compare1);
	stable_sort(str, str+num, compare2);
	for (int i = 0; i < num; i++)
	{
		if (str[i] == str[i - 1] && i - 1 >= 0)
			continue;
		cout << str[i] << "\n";
	}
	return 0;
}

1181번 문제의 경우 두 가지 정렬 조건을 수행해야 한다.

1. 길이 순

2. 사전 순

위의 소스를 보면 compare1은 사전순으로 오름차순 정렬을 수행하게 되는 조건이고,

 

compare2는 길이순으로 오름차순 정렬을 수행하게 되는 조건이다.

 

하지만 main함수에서 수행하는 sort의 종류가 다르다.

 

우선 사전 순으로 기본 sort함수를 수행하고, 길이 순으로 stable_sort를 수행하는데

이렇게 하는 이유는 첫번째 정렬을 수행할 때에는 순서가 상관이 없이 정렬되어도 상관 없지만, 두번째 정렬을 수행할 때에는 앞서 얻게 된 결과의 순서를 지킬 필요가 있기 때문이다.

 

두 번째 정렬일 진행될 때 같은 길이의 단어가 입력될 경우 둘 다 sort 함수를 사용하게 되면 사전 순서대로 정렬된 값의 순서가 뒤죽박죽이 되기 때문에 문제에서는 당연히 오답처리가 된다.

 

이렇듯 중복된 조건의 값이 많고 순서를 유지 해야하는 경우 stable_sort를 적절히 활용해 주는 것이 좋다.

 

물론 algorithm에서는 이 두가지의 정렬 함수 말고도 여러가지 함수가 더 존재한다.

-std::inplace_merge(first, middle, end)
기존의 std::merge 달리 파라메터로 넘겨준 데이터를 함수 안에서 직접 수정.
파라미터로 first, middle, end 세 가지를 받으며 양방향 반복.
복잡도 : begin - middle , middle - end가 따로 정렬이 되어있을 경우 O(N)

-std::partial_sort(begin, middle, end)
start~middle 까지만 정렬한 후 나머지는 정렬하지 않는 함수.
최상위 몇 개의 값만 추출하거나 할 때 유용한 정렬.
불안정정렬
복잡도 : O ((last-first) log (mid-first))

-std::nth_element(begin, middle, end)
middle 값을 기준으로 그 기준보다 작은 것들은 왼쪽, 큰 것들은 오른쪽으로 정렬.
불안정정렬
복잡도 :(last-first)

-std::is_sorted(begin, end, compare)
한 컨테이너가 compare의 조건대로 정렬되어 잇는지 확인하는 함수