,
,
,
,
,
,
,
,
,
은(는) 여기로 연결됩니다. 1. 개요
整列 / sorting, ordering무언가가 임의의 순서로 주어졌을 때 내용물을 정해진 순서대로 가지런하게 나열하는 것.
2. 용례
나열하는 순서(차순)에 따라서 오름차순(ascending order), 내림차순(descending order)으로 구분한다. 오름차순은 1 → 2 → 3 → 4 → …… 와 같이 뒤로 갈수록 숫자가 커지는 경우이고 내림차순은 그 반대다. 사람들이 자주 헷갈려하는데 정렬한 결과물을 선그래프로 그렸을 때 값이 작은 것을 앞으로 정렬하면 그래프의 선이 올라가므로(↗) 오름차순이고 값이 큰 것을 앞으로 정렬하면 그래프의 선이 내려가므로(↘) 내림차순이라고 생각하면 된다. 마찬가지로 어휘의 순서를 기반으로 가나다 → ABC 순으로 나열하는 경우에는 오름차순이고, 그 반대의 경우에는 내림차순에 해당한다.나무위키는 문서를 작성하고 예시들을 기재할 때 대한민국의 행정구역 정렬[1] 등 특별한 경우가 아니면 보통 가나다순 → ABC순 정렬을 권장하고 있다.
3. 정렬가능성
일반적으로 임의의 자료를 정렬 가능하려면 모든 자료의 집합 [math(A)]에 대해 전순서 관계 [math(\preceq)]이 모든 [math(a,\,b\in A)]에 대해 항상 정의(strongly connected)되어야 하며, 이를 만족하는 집합 [math(A)]를 전순서 집합(totally ordered set) 또는 선형 순서 집합(linearly ordered set)이라고 한다. 구체적인 조건은 다음과 같다.- 반사성(reflexivity): [math(\forall a\in A(a\preceq a))][2]
- 반대칭성(antisymmetricity): [math(\forall a,b\in A(a\preceq b\land b\preceq a\to a=b))]
- 추이성(transitivity): [math(\forall a,b,c\in A(a\preceq b\land b\preceq c\to a\preceq c))]
- 강한 연결성(strongly connected): [math(\forall a,b\in A(a\preceq b\lor b\preceq a))]
예를 들어 가위바위보의 경우, 자신은 자기 자신과 비기고(반사성) 임의의 두 행동에 대해 반드시 승패(비기는 것 포함)가 정의되어 있으며, [math((a\preceq b \land b \preceq a) \to a \neq b)]인 상황도 존재하지 않으므로 반대칭성도 성립한다. 하지만 추이성만은 성립하지 않는다. 바위는 가위를 이기고(가위 [math(\preceq)] 바위) 보는 바위를 이기지만(바위 [math(\preceq)] 보) 보가 가위도 이기는 것은 아니기 때문이다(가위 [math(\not\preceq)] 보). 따라서 {가위, 바위, 보}로 이루어진 집합은 전순서 집합이 아니다.
이런 경우 [가위, 바위, 보]로 이루어진 벡터가 존재할 때, 가능한 정렬 결과는 [가위, 바위, 보], [바위, 보, 가위], [보, 가위, 바위] 등 여러 개가 될 수 있다. 유향 그래프로 보면 더욱 명확해지는데, 가위 바위 보 끼리 서로 순환하는(cyclic) 그래프를 이루게 된다. 어째서 전순서 집합의 다른 명칭이 선형 순서 집합(linearly ordered set)인지 알 수 있는 대목이다.
또 다른 예시로 IEEE 표준 부동소수점의 경우, [math(\rm NaN\neq NaN\land NaN\not\leq NaN\land NaN\not\geq NaN)]로 NaN에서 올바른 순서 관계가 정의되지 않기 때문에 일반적으로[3] 부동소수점의 벡터는 정렬할 수 없다.
4. 종류
4.1. 비교 정렬과 비비교 정렬
Comparison sort & Non-comparison sort
위에서 설명한 전순서 관계를 활용하면, 임의의 요소 [math(a)]와 [math(b)]에 대해 항상 누가 앞에 오고 누가 뒤에 오는지를 알 수 있다. 이를 활용하는 것이 바로 비교 정렬이다. 반대로 비교 연산을 사용하지 않는 정렬은 비비교 정렬, 일반 정렬 등으로 불린다.
이 성질을 이용하면 비교 정렬의 최소 시간 복잡도를 알 수 있다.
우선 정렬하고자 하는 유한집합 [math(A')]이 전순서 집합 [math(A)]의 크기가 [math(|A'|=n)]인 부분집합일 때, 모든 원소가 서로 다르므로 가능한 순열의 개수는 [math(_n{\rm P}_n=n!)]이며 이중 단 하나만이 올바른 정렬 결과일 것이다. 임의의 [math(a)]와 [math(b)]의 비교는 이항 관계이므로 올바른 정렬을 찾기 위한 비교 연산의 최소 횟수는 2의 거듭제곱으로 늘어난다. 따라서 정렬이 적어도 [math(f(n))]번 안에 끝난다면 결정 트리의 최대 폭은 [math(2^{f(n)})]이 되며 검증해야 하는 최대 조합 수는 [math(n!)]이므로,
[math(2^{f(n)}\ge n!\Rightarrow f(n)\ge\operatorname{lb}n!)]
이제 스털링 근사를 사용해 [math(n!)]을 근사하면
[math(\operatorname{lb}n!\ge\operatorname{lb}\left(\dfrac n2\right)^{\frac n2}=\dfrac n2\operatorname{lb}\dfrac n2=\dfrac n2\Bigl(\operatorname{lb}n-\operatorname{lb}2\Bigr)=\dfrac n2\operatorname{lb}n-\dfrac n2\approx\mathcal O(n\log n))]
비교 연산의 실행 횟수 [math(f(n))]의 하한이 [math(n\log n)]에 근사하므로 모든 비교 정렬 알고리즘은 아무리 빨라도 [math(\mathcal O(n\log n))] 보다 빠를 수 없음을 알 수 있다.
비비교 정렬의 경우 특수한 환경에서 [math(\mathcal O(n\log n))]보다 빠른 효율을 보이기도 하지만, 일반적으로 적용되기에는 비교 정렬에 비해 여러 제약이 존재한다.
예를 들어 대표적인 비비교 정렬 중 하나인 계수 정렬(counting sort)의 경우, [math(\mathcal O(n))]이라는 매우 빠른 속도를 가지지만 유한한 범위의 양의 정수[4] 집합에서만 성립한다. 실수의 경우 항상 두 실수 사이에 무한한 실수가 존재할 수 있어 인덱싱이 의미가 없기 때문이다.