문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 정렬 (문단 편집) == 정렬가능성 == 일반적으로 임의의 자료를 정렬 가능하려면 모든 자료의 집합 [math(A)]에 대해 [[순서 관계#s-2|전순서 관계]] [math(\preceq)]이 모든 [math(a,\,b\in A)]에 대해 항상 정의(strongly connected)되어야 하며, 이를 만족하는 집합 [math(A)]를 [[순서 관계#s-4|전순서 집합]](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)인지 알 수 있는 대목이다. 또 다른 예시로 [[컴퓨터에서의 수 표현#s-4|IEEE 표준 부동소수점]]의 경우, [math(\rm NaN\neq NaN\land NaN\not\leq NaN\land NaN\not\geq NaN)]로 [[NaN]]에서 올바른 순서 관계가 정의되지 않기 때문에 일반적으로[* 물론 이는 이론상의 이야기이며, 언어별로 해결책은 다르거나 아예 별 문제없이 정렬되는 언어도 있다. 일반적으론 각 언어별 표준 라이브러리에서 이미 해결된 방법이 있기 때문에 그걸 사용하거나 정 안된다 싶으면 비교 함수를 직접 손으로 짜는 방법도 있다.] 부동소수점의 벡터는 정렬할 수 없다. [include(틀:상세 내용, 문서명=순서 관계)]저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기