정렬

덤프버전 :

1. 개요
2. 용례
3. 정렬가능성
4. 종류
4.1. 비교 정렬과 비비교 정렬
4.2. 안정 정렬과 불안정 정렬
5. 정렬 순서
6.1. 부분 순서 집합의 정렬 알고리즘
7. 관련 항목




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)]


예를 들어 가위바위보의 경우, 자신은 자기 자신과 비기고(반사성) 임의의 두 행동에 대해 반드시 승패(비기는 것 포함)가 정의되어 있으며, [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] 부동소수점의 벡터는 정렬할 수 없다.
파일:나무위키상세내용.png   자세한 내용은 순서 관계 문서를 참고하십시오.



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!)]
[1] 이쪽은 행정안전부의 행정구역코드를 우선적으로 사용한다.[2] 물론 이는 이론상의 이야기이며, 언어별로 해결책은 다르거나 아예 별 문제없이 정렬되는 언어도 있다. 일반적으론 각 언어별 표준 라이브러리에서 이미 해결된 방법이 있기 때문에 그걸 사용하거나 정 안된다 싶으면 비교 함수를 직접 손으로 짜는 방법도 있다.


이제 스털링 근사를 사용해 [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. 안정 정렬과 불안정 정렬[편집]


파일:나무위키상세내용.png   자세한 내용은 정렬 알고리즘 문서를 참고하십시오.



5. 정렬 순서[편집]


상술한 비교 정렬을 하려면 임의의 두 값 [math(a)]와 [math(b)]중 어느 쪽이 먼저 오는지를 알 수 있어야 한다. 일반적인 정수 정렬의 경우 쉽게 대소를 비교할 수 있지만 만일 그것이 문자, 그림, 가족관계 등 복잡한 자료라면 별도의 기준이 필요하다. 이때 사용하는 것이 바로 정렬 순서이다.


5.1. 차순[편집]


논리적으로 '작은 것부터 큰 순으로', '큰 것부터 작은 순으로' 등 정렬된 결과의 방향을 정할 때 차순이 필요하다.
파일:나무위키상세내용.png   자세한 내용은 차순 문서를 참고하십시오.


5.2. 문자 정렬 순서[편집]


파일:나무위키상세내용.png   자세한 내용은 정렬/순서 문서를 참고하십시오.


6. 정렬 알고리즘[편집]


파일:나무위키상세내용.png   자세한 내용은 정렬 알고리즘 문서를 참고하십시오.



6.1. 부분 순서 집합의 정렬 알고리즘[편집]


파일:나무위키상세내용.png   자세한 내용은 위상 정렬 문서를 참고하십시오.



7. 관련 항목[편집]



파일:크리에이티브 커먼즈 라이선스__CC.png 이 문서의 내용 중 전체 또는 일부는 2023-12-16 09:07:11에 나무위키 정렬 문서에서 가져왔습니다.

[3] 범위가 유한하다면 적절한 처리를 통해 음수도 가능하다.