1. 개요
整列 / Sorting뭔가가 주어졌을 때 이것을 정해진 순서대로 가지런하게 나열하는 것을 의미한다.
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)이라고 한다. 구체적인 조건은 다음과 같다.1. 반사성(reflexivity): [math((\forall a \in A)\ a \preceq a)]
1. 반대칭성(antisymmetricity): [math((\forall a,b \in A)\ a \preceq b \land b \preceq a \to a = b)]
1. 추이성(transitivity): [math((\forall a,b,c \in A)\ a \preceq b \land b \preceq c \to a \preceq c)]
1. 강한 연결성(strongly connected): [math((\forall a,b \in A)\ a \preceq b \lor b \preceq a)]
1. 반대칭성(antisymmetricity): [math((\forall a,b \in A)\ a \preceq b \land b \preceq a \to a = b)]
1. 추이성(transitivity): [math((\forall a,b,c \in A)\ a \preceq b \land b \preceq c \to a \preceq c)]
1. 강한 연결성(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에서 올바른 순서 관계가 정의되지 않기 때문에 일반적으로[2] 부동소수점의 벡터는 정렬할 수 없다.
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))]이라는 매우 빠른 속도를 가지지만 유한한 범위의 양의 정수[3] 집합에서만 성립한다. 실수의 경우 항상 두 실수 사이에 무한한 실수가 존재할 수 있어 인덱싱이 의미가 없기 때문이다.
4.2. 안정 정렬과 불안정 정렬
5. 정렬 순서
상술한 비교 정렬을 하려면 임의의 두 값 [math(a)]와 [math(b)]중 어느 쪽이 먼저 오는지를 알 수 있어야 한다. 일반적인 정수 정렬의 경우 쉽게 대소를 비교할 수 있지만 만일 그것이 문자, 그림, 가족관계 등 복잡한 자료라면 별도의 기준이 필요하다. 이때 사용하는 것이 바로 정렬 순서이다.5.1. 차순
논리적으로 '작은 것부터 큰 순으로', '큰 것부터 작은 순으로' 등 정렬된 결과의 방향을 정할 때 차순이 필요하다.5.2. 문자 정렬 순서
6. 정렬 알고리즘
6.1. 부분 순서 집합의 정렬 알고리즘
7. 정렬 알고리즘 비교
유튜브 등의 영상 플랫폼에서 꾸준히 유행하는 콘텐츠다. 정렬되는 모습에 음향 효과를 끼워넣으니 은근 중독성이 있고, 불멍이라도 하는 것처럼 아무 생각 없이 구경하게 된다. 초창기에는 날카로운 기계음 효과를 넣었으나 이후에는 아무 생각 없이 구경하기 용이하도록 비교적 부드러운 음향효과를 넣고 있다.