01. Stable, Unstable Sort

- Stable Sort(안정 정렬)

 a. 동일한 정렬 기준을 가진 것은 정렬하기 전의 순서와 정렬한 후의 순서가 동일한 것이다.

age	name
200	A
200	B
200	C
200	D
200	E
200	F
200	G
10	Z
11	Z
....	Z
99	Z

예를 들면 이러한 나이, 이름의 표가 있다고 가정하자.

 

여기서 Stable한 Sorting이 age를 기준으로 이뤄진다면 다음과 같은 결과가 나온다.

age	name
10	Z
11	Z
...	Z
99	Z
200	A
200	B
200	C
200	D
200	E
200	F
200	G

<그림> STL: std::stable_sort로 정렬한 결과

- Unstable Sort(불안정 정렬)

a. 동일한 정렬 기준을 가진 것이 정렬하기 전의 순서와 정렬한 후의 순서가 보장되지 않는다.

위의 표를 생각했을때 정렬 알고리즘에 따라 age가 200인 name의 순서가 어떻게 될지는 알고리즘에 따라 다르다고 할 수 있다.

<그림> STL std::sort로 정렬한 결과

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
struct SortingTest {
	int age;
	char name;
};
bool operator<(const SortingTest& lhs, const SortingTest& rhs)
{
	return lhs.age < rhs.age;
};
int main(void)
{
	std::vector<SortingTest> v{
		{200,'A'},
		{200,'B'},
		{200,'C'},
		{200,'D'},
		{200,'E'},
		{200,'F'},
		{200,'G'},
	};
	for (int i = 10; i < 100; i++)
		v.emplace_back(SortingTest{ i, 'Z' });
	std::stable_sort(v.begin(), v.end());
	//std::sort(v.begin(), v.end());
	for (const SortingTest e : v)
	{
		std::cout << e.age << ", " << e.name << "\n";
	}

	return 0;
}

<예제 소스 코드>

- 정리

C++ STL에서는 stable_sort를 자체적으로 제공하고 있다. 

아래는 각종 정렬 알고리즘이 Stable한지 Unstable한지를 정리한 것이다.

StableSort	UnstableSort
Bubble Sort(버블 정렬)	Selection Sort (선택 정렬)
Insertion Sort(삽입 정렬)	Quick Sort (퀵 정렬)
Merge Sort(합병 정렬)	Heap Sort (힙 정렬)
STL std::stable_sort	STL std::sort

 

STL의 std::stable_sort는 MergeSort(합병 정렬) 기반으로 이루어져 있다.

 

STL의 std::sort는 QuickSort(퀵 정렬) 기반으로 이루어져 있지만, QuickSort의 한계점인 최악의 시간 복잡도가 O(n^2)인 것을 극복하기 위해 라이브러리에서는 다양한 구현이 이루어진다.

 - 피벗을 랜덤으로 택할 수 있다.

 - 피벗 후보를 여러개 정해서 그 중 중앙값을 둘 수 있다.

 - 최악을 피하기 위해 일정 깊이 이상 들어가면 QuickSort 대신 HeapSort로 정렬을 시작한다.

 - 이러한 정렬은 Introspective sort라고 한다.

 

코딩테스트에서 STL Sort를 사용하기 위해서는 stable이 필요하다면 stable_sort, 그게 아니라 nlogn이 필요하다면 sort를 사용해도 된다.

 

STL 라이브러리가 사용이 불가능하다면 mergeSort를 직접 구현을 하는 것을 추천한다.

(퀵정렬은 한계가 있다.)

 

 

Reference

- 코드 없는 프로그래밍(NoCodeProgramming)

- BaaarkingDog