#!if 넘어옴1 != null
''''''{{{#!if 넘어옴2 != null
, ''''''}}}{{{#!if 넘어옴3 != null
, ''''''}}}{{{#!if 넘어옴4 != null
, ''''''}}}{{{#!if 넘어옴5 != null
, ''''''}}}{{{#!if 넘어옴6 != null
, ''''''}}}{{{#!if 넘어옴7 != null
, ''''''}}}{{{#!if 넘어옴8 != null
, ''''''}}}{{{#!if 넘어옴9 != null
, ''''''}}}{{{#!if 넘어옴10 != null
, ''''''}}}은(는) 여기로 연결됩니다. #!if 설명 == null && 리스트 == null
{{{#!if 설명1 == null
다른 뜻에 대한 내용은 아래 문서를}}}{{{#!if 설명1 != null
{{{#!html 이 문서는 순서 정렬(sort)에 대해 다룹니다. 배치 정렬(align)}}}에 대한 내용은 [[나무위키:문법 도움말/심화]] 문서{{{#!if (문단1 == null) == (앵커1 == null)
를}}}{{{#!if 문단1 != null & 앵커1 == null
의 [[나무위키:문법 도움말/심화#s-|]]번 문단을}}}{{{#!if 문단1 == null & 앵커1 != null
의 [[나무위키:문법 도움말/심화#텍스트 정렬|텍스트 정렬]] 부분을}}}}}}{{{#!if 설명2 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단2 == null) == (앵커2 == null)
를}}}{{{#!if 문단2 != null & 앵커2 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단2 == null & 앵커2 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명3 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단3 == null) == (앵커3 == null)
를}}}{{{#!if 문단3 != null & 앵커3 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단3 == null & 앵커3 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명4 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단4 == null) == (앵커4 == null)
를}}}{{{#!if 문단4 != null & 앵커4 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단4 == null & 앵커4 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명5 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단5 == null) == (앵커5 == null)
를}}}{{{#!if 문단5 != null & 앵커5 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단5 == null & 앵커5 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명6 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단6 == null) == (앵커6 == null)
를}}}{{{#!if 문단6 != null & 앵커6 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단6 == null & 앵커6 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명7 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단7 == null) == (앵커7 == null)
를}}}{{{#!if 문단7 != null & 앵커7 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단7 == null & 앵커7 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명8 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단8 == null) == (앵커8 == null)
를}}}{{{#!if 문단8 != null & 앵커8 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단8 == null & 앵커8 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명9 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단9 == null) == (앵커9 == null)
를}}}{{{#!if 문단9 != null & 앵커9 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단9 == null & 앵커9 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명10 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단10 == null) == (앵커10 == null)
를}}}{{{#!if 문단10 != null & 앵커10 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단10 == null & 앵커10 != null
의 [[#|]] 부분을}}}}}}#!if 설명 == null
{{{#!if 리스트 != null
다른 뜻에 대한 내용은 아래 문서를}}} 참고하십시오.#!if 리스트 != null
{{{#!if 문서명1 != null
* {{{#!if 설명1 != null
이 문서는 순서 정렬(sort)에 대해 다룹니다. 배치 정렬(align): }}}[[나무위키:문법 도움말/심화]] {{{#!if 문단1 != null & 앵커1 == null
문서의 [[나무위키:문법 도움말/심화#s-|]]번 문단}}}{{{#!if 문단1 == null & 앵커1 != null
문서의 [[나무위키:문법 도움말/심화#텍스트 정렬|텍스트 정렬]] 부분}}}}}}{{{#!if 문서명2 != null
* {{{#!if 설명2 != null
: }}}[[]] {{{#!if 문단2 != null & 앵커2 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단2 == null & 앵커2 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명3 != null
* {{{#!if 설명3 != null
: }}}[[]] {{{#!if 문단3 != null & 앵커3 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단3 == null & 앵커3 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명4 != null
* {{{#!if 설명4 != null
: }}}[[]] {{{#!if 문단4 != null & 앵커4 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단4 == null & 앵커4 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명5 != null
* {{{#!if 설명5 != null
: }}}[[]] {{{#!if 문단5 != null & 앵커5 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단5 == null & 앵커5 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명6 != null
* {{{#!if 설명6 != null
: }}}[[]] {{{#!if 문단6 != null & 앵커6 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단6 == null & 앵커6 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명7 != null
* {{{#!if 설명7 != null
: }}}[[]] {{{#!if 문단7 != null & 앵커7 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단7 == null & 앵커7 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명8 != null
* {{{#!if 설명8 != null
: }}}[[]] {{{#!if 문단8 != null & 앵커8 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단8 == null & 앵커8 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명9 != null
* {{{#!if 설명9 != null
: }}}[[]] {{{#!if 문단9 != null & 앵커9 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단9 == null & 앵커9 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명10 != null
* {{{#!if 설명10 != null
: }}}[[]] {{{#!if 문단10 != null & 앵커10 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단10 == null & 앵커10 != null
문서의 [[#|]] 부분}}}}}}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] 부동소수점의 벡터는 정렬할 수 없다.
#!if (문단 == null) == (앵커 == null)
를#!if 문단 != null & 앵커 == null
의 [[순서 관계#s-|]]번 문단을#!if 문단 == null & 앵커 != null
의 [[순서 관계#|]][[순서 관계#|]] 부분을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] 집합에서만 성립한다. 실수의 경우 항상 두 실수 사이에 무한한 실수가 존재할 수 있어 인덱싱이 의미가 없기 때문이다.
4.2. 안정 정렬과 불안정 정렬
#!if (문단 == null) == (앵커 == null)
를#!if 문단 != null & 앵커 == null
의 [[정렬 알고리즘#s-3|3]]번 문단을#!if 문단 == null & 앵커 != null
의 [[정렬 알고리즘#|]][[정렬 알고리즘#|]] 부분을5. 정렬 순서
상술한 비교 정렬을 하려면 임의의 두 값 [math(a)]와 [math(b)]중 어느 쪽이 먼저 오는지를 알 수 있어야 한다. 일반적인 정수 정렬의 경우 쉽게 대소를 비교할 수 있지만 만일 그것이 문자, 그림, 가족관계 등 복잡한 자료라면 별도의 기준이 필요하다. 이때 사용하는 것이 바로 정렬 순서이다.5.1. 차순
논리적으로 '작은 것부터 큰 순으로', '큰 것부터 작은 순으로' 등 정렬된 결과의 방향을 정할 때 차순이 필요하다.#!if (문단 == null) == (앵커 == null)
를#!if 문단 != null & 앵커 == null
의 [[차순#s-|]]번 문단을#!if 문단 == null & 앵커 != null
의 [[차순#|]][[차순#|]] 부분을5.2. 문자 정렬 순서
#!if (문단 == null) == (앵커 == null)
를#!if 문단 != null & 앵커 == null
의 [[정렬/순서#s-|]]번 문단을#!if 문단 == null & 앵커 != null
의 [[정렬/순서#|]][[정렬/순서#|]] 부분을6. 정렬 알고리즘
#!if (문단 == null) == (앵커 == null)
를#!if 문단 != null & 앵커 == null
의 [[정렬 알고리즘#s-|]]번 문단을#!if 문단 == null & 앵커 != null
의 [[정렬 알고리즘#|]][[정렬 알고리즘#|]] 부분을6.1. 부분 순서 집합의 정렬 알고리즘
#!if (문단 == null) == (앵커 == null)
를#!if 문단 != null & 앵커 == null
의 [[위상 정렬#s-|]]번 문단을#!if 문단 == null & 앵커 != null
의 [[위상 정렬#|]][[위상 정렬#|]] 부분을