PS에서의 정렬에 대한 고찰

정렬이란 무엇인가?

 

정렬은 집합 속 모든 원소들을 순서대로 나열하는 것이다.

 

정렬은 꼭 수를 정렬할 때만 쓰이는 것은 아니다.

 

영어 단어들은 알파벳 사전순으로 정렬할 수 있고 한국어 단어들은 가나다순으로 정렬할 수 있다.

 

정렬 알고리즘은 여러가지가 있다. 프로그래밍을 처음 입문하면서 배우는 버블 정렬, 선택 정렬, 삽입 정렬과 퀵 정렬, 합병 정렬, 힙 정렬 등 매우 많이 존재한다.

 

하지만 오늘은 이런 정렬 알고리즘에 대해 소개하지는 않을 것이다.

 

간단하게 언급만 하자면 정렬할 원소의 개수가 \(n\)일 때, 버블/선택/삽입 정렬은 \(O(n^2)\)의 시간복잡도를, 합병/힙 정렬은 \(O(n\log n)\)의 시간복잡도를 가진다. 퀵 정렬은 좀 더 생각해봐야 될 점이 있기 떄문에 여기서는 언급하지 않으려고 한다.

 

PS에서 정렬 알고리즘을 구현하는 것은 크게 중요하지 않다고 생각한다.

 

이미 잘 구현된 정렬 함수를 쓰면 되는 일이기 떄문이다.

 

게다가 비교 기반 정렬이 아무리 빨라봐야 \(O(n\log n)\)보다 빠를 수 없다는 사실은 이미 증명된 사실이다.

 

여기서 "비교 기반" 정렬이라는 단어가 등장하는데 비교라는 것을 하려면 집합의 원소 사이에 순서가 정의되어야 한다.

 

순서에는 여러가지가 있지만 C++ STL의 std::sort 안에 쓰는 비교함수는 Strict weak ordering을 만족해야한다.

 

집합 \(S\) 위에 이항 관계 \(<\)를 다음과 같은 집합으로 생각할 수 있다.

 

\[<\:\subsetneq S\times S\]

 

이렇게 정의하면 \(x<y\)는 \((x,y)\in\:<\)를 의미한다.

 

그리고 비교함수의 의미는 만약 \(x<y\)이면 \(x\)가 \(y\)보다 먼저온다는 뜻이다.

 

만약 \(x<y\)와 \(y<x\)가 모두 거짓이면 \(x\)와 \(y\)는 비교 불가하다는 뜻이다. 하지만 \(x\)와 \(y\)가 같은 원소라는 뜻은 아니다.

 

Strict weak ordering은 4가지 조건을 만족해야한다.

 

1. 비반사성

모든 \(x\in S\)에 대하여 \(x<x\)는 거짓이다.

 

앞에서 언급한 비교함수에 의미를 잠깐 보면

 

만약 \(x<x\)이 참이라면, \(x\)가 \(x\)보다 먼저와야하는데 이는 불가능하므로 잘 맞아떨어지는 것을 알 수 있다.

 

2. 추이성

모든 \(x,y,z\in S\)에 대하여 만약 \(x<y\)이고 \(y<z\)이면, \(x<z\)이다.

 

당연하게 느껴질 수도 있다. 그렇다면 이것을 생각해보자.

 

\(S=\{\rm가위, 바위, 보\it\}\)를 정렬 한다고 해보자.

 

만약 비교함수를 다음과 같이 정의한다면 어떻게 될지 생각해보자.

 

\(x\)가 \(y\)를 이긴다면 참, 그렇지 않다면 거짓

 

\(\rm가위\it<\rm보\), \(\rm보\it<\rm바위\)인데 \(\rm가위\it<\rm바위\)는 거짓이다.

 

만약에 비교함수를 다음과 같이 정의하면 어떨까?

 

\(x\)가 \(y\)보다 펴진 손가락의 개수가 많다면 참, 그렇지 않다면 거짓

 

이제야 정렬이 가능해졌음을 알 수 있다.

 

예제를 통해서 비교함수를 어떻게 설정하는지가 매우 중요함을 알 수 있다.

 

3. 비대칭성

모든 \(x,y\in S\)에 대하여 만약 \(x<y\)가 참이면 \(y<x\)는 거짓이다.

 

비교함수로 \(x\leq y\)를 사용할 수 없는 이유이기도 하다.

 

4. 비비교성의 추이성

모든 \(x,y,z\in S\)에 대하여 만약 \(x\)와 \(y\)가 비교 불가능하고 \(y\)와 \(z\)가 비교 불가능하다면, \(x\)와 \(z\)도 비교 불가능하다.

 

백준에서 다음 문제를 풀어보면 이해하는데 조금 도움이 될 수도 있다.

13316번: std::정렬부터 시작하는 디버깅 생활

 

연습문제

16496번: 큰 수 만들기

 

 

참고로 비교가 불가능한 서로 다른 원소들 사이의 순서를 정렬하기 전 순서로 유지하는 것을 Stable sort라고 하고 C++ STL의 함수 std::stable_sort를 사용할 수 있다. 하지만 메모리 공간이 충분하지 않은 경우 조금 더 느리다 \(O(n\log^2 n)\)

 

(이는 어떻게 생각하면 원래는 비교가 불가능한 서로 다른 원소들 사이의 순서를 정해 원래 이항 관계에 합집합 한 것과 같다.)