stable sort과 unstable sort

정렬을 하다 보면 이런 문제들이 있다.

www.acmicpc.net/problem/10814

10814번: 나이순 정렬

나이가 증가하는 순서로 정렬을 하지만 만약에 나이가 같다면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 문제

이러한 문제처럼 먼저 들어온 사람이 먼저 출력되는 것을 아래와 같이 정리할 수 있다.

정렬되지 않은 상태에서 같은 키(나이) 값을 가진 원소의 순서가 정렬 후에도 유지가 되는가?

이러한 개념이 바로 Stable Sort 이라고 하며 안정된 정렬이라고 불린다.

Stable Sort는 정렬이 되어서도 같은 키값이라도 먼저 들어온 녀석이 먼저 앞에 있는다.

같은 키를 가진 사람이 A B 가 있는데, 정렬 후에도 이 순서는 유지가 된다는 것이다.

 

반대로 Unstable Sort 는 불안정된 정렬이며 정렬 후에는 이 순서가 무너질 수 있다.

같은 키를 가진 사람이 A B 순서로 도착했지만 어떠한 경우에서 B A 순서가 될 수 있다.

먼저 온 A 입장에서는 억울한 경우이다.

 

이처럼 문제에서 안정된 정렬을 요구하는 문제들이 있다.

이러한 안정된 정렬을 알고리즘에서 써먹으려면 어떻게 할까?

STL에서는 stable_sort를 따로 지원해준다.

https://en.cppreference.com/w/cpp/algorithm/stable_sort

이 코드를 따라 쳐보면 다음과 같이 안정된 정렬이 출력되는 것을 확인할 수 있다.

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

struct Employee
{
	int age;
	string name;
};

bool operator<(const Employee& a, const Employee& b)
{
	return a.age < b.age;
}

int main()
{
	vector<Employee> v =
	{
		{27, "Uade"},
		{19, "Dopa"},
		{27, "Papa"}
	};

	// 안정 정렬
	stable_sort(v.begin(), v.end());

	for (const Employee& e : v)
		cout << e.age << ' ' << e.name << '\n';
	return 0;
}

19 Dopa
27 Uade
27 Papa

출력 결과를 보면 같은 나이 27살 친구가 "Uade"와 "Papa"가 있는데

먼저 들어온 친구의 이름은 "Uade" 이므로

같은 나이 경우에서는 "Uade" 가 먼저 나오는 것을 확인할 수 있다.

 

알고리즘 파트를 공부하면 많은 정렬법에 대해서 배우게 된다.

여기서도 안정된 정렬과 불안정된 정렬을 구분할 수 있다.

 

안정한 정렬 Stable Sort

Insertion Sort 삽입 정렬	정렬되지 않은 원소를 선택해서 정렬된 자리를 잘 찾아서 삽입하는 알고리즘이다. 이 때 Swap 과정이 일어나지 않으므로 안정된 정렬이다.
Merge Sort 병합 정렬	크기가 N인 배열을 1 / 2 씩 쪼개면서 분할(divide) 과정을 반복한다. 이 반복은 배열의 크기가 1이 될 때까지 반복한다. 분할 과정이 끝났다면 정복(Conquer) 과정을 통해 정렬된 배열을 합친다. 이 때 Swap 과정이 일어나지 않으므로 안정된 배열이다.
Bubble Sort 버블 정렬	두 개의 원소를 비교하면서 앞의 원소가 뒤의 원소보다 크다면 Swap 한다. 여기서의 Swap 은 자신과 왼쪽 혹은 오른쪽과 Swap 하는 과정이기 때문에 안정성을 깨트리지 않는 정렬이다. 그렇게 비교하면서 작은 원소를 앞으로 보내는 정렬이므로 안정된 정렬이다.
Counting Sort 카운팅 정렬	카운팅 정렬은 메모리 공간을 사용해서 해당 원소가 등장하면 그 등장한 횟수만큼 메모리에 저장했다가 순서대로 꺼내서 출력하여 정렬을 완성하는 정렬법이다. 저장했다가 순서대로 꺼내기 때문에 안정된 정렬이다.

불안정한 정렬 Unstable Sort

Selection Sort 선택 정렬	가장 작은 원소를 찾아서 가장 알맞은 위치를 찾아 그 위치와 현재 위치를 Swap 해가며 정렬해간다. 이 과정에서 안정성을 깨트리므로 불안정한 정렬이다.
Heap Sort 힙 정렬	Min-heap 을 기준으로 생각해보자. 이미 Heap에 새로운 원소가 들어온다고 했을 때 아래 말단 노드부터 루트 노드까지 부모 노드와 비교하면서 들어온 노드가 부모 노드보다 더 작은 노드라면 Swap 하는 과정이 들어가게 된다. 이 때 이미 같은 노드의 값이 미리 Heap에 들어있는데 들어온 노드가 어쩌다보니 루트 노드의 자식 노드까지 들어가게 된 경우 배열 index 기준으로 먼저 들어온 값의 index 보다 나중에 들어온 index 가 역전되는 현상이 생긴다. 따라서 불안정한 정렬이다.
Quick Sort 퀵 정렬	가장 앞의 원소를 pivot 으로 잡고 생각해보자. pivot 을 기준으로 left 포인터는 pivot 보다 큰 원소를 찾고 right 포인터는 pivot 보다 작은 원소를 찾아 left 와 right 를 swap 해가면서 정렬을 한다. 이 경우에서 Swap으로 인해 안정성을 깨트리므로 불안정한 정렬이다.

 

In place Sort

추가적으로 정렬 알고리즘을 공부하다 보면 In-place Sort라는 용어를 듣게 된다.

In-place라는 말은 정렬을 하는 과정에서 추가적인 메모리를 사용하지 않는 것을 의미한다.

 

대표적으로 Bubble Sort 경우 추가적인 메모리 필요 없이 인접한 원소를 끼리 비교하고 서로 Swap 하므로

메모리 공간의 복잡도는 O(1) 이 된다.

 

반대로 Merge Sort 경우 대표적인 Not in place이다.

합병 정렬하는 과정에서 N개의 Problem을 1 / 2 로 쪼개 각각의 SubProblem을 분할해가며,

나중에 정렬된 두 개의 SubProblem 을 Merge 하는 과정에서 추가적인 메모리 공간이 필요하게 된다.

메모리 공간의 복잡도는 O(N)이다.

 

In place Sort

Insertion Sort	O(1) 메모리 공간이 필요한 경우는 정렬되지 않은 원소를 하나 선택하게 되는데 이 때 값을 기억하는 공간이 필요하다. 이후 그 자리를 만들어주도록 원소들이 한 칸씩 오른쪽으로 이동하고 기억한 공간을 그 원소에 삽입하면서 정렬한다.
Selection Sort	O(1) 작은 원소를 찾아서 정렬하려는 위치와 Swap한다. Swap 하는 과정에서 Temp 라는 공간이 필요하다.
Bubble Sort	O(1) 인접한 두 원소를 Swap 하는 과정에서 Temp 라는 공간이 필요하다.
Heap Sort	O(1) 부모 노드와 자식 노드를 비교하는 과정에서 만약 Swap이 필요하다면 Temp 라는 공간이 필요하다.
Quick Sort	O(1) 우선 pivot 이라는 공간과 left right 서로 Swap 할 Temp 공간이 필요하다.

Not In place Sort

Merge Sort	O(N) Merge 하는 과정에서 추가적인 메모리 공간이 필요하다.
Counting Sort	O(N) 정렬 기법중 선형 시간안에 정렬할 수 있지만 추가적인 메모리 공간이 필요한 정렬기법이다. 공간을 사용하므로써 시간을 줄이는 기법이다.
Radix Sort	O(N) Bucket 이라는 공간을 사용한다. 추가적인 메모리 공간이 필요한 정렬 기법이다.