위키득계정 ↗
기술

정렬 안정성과 정렬 키

정렬 안정성과 정렬 키기술
정렬 키
항목에서 비교할 기준값
안정성
동률 항목의 기존 상대 순서 유지
다중 기준
기준의 우선순위 명시
주의점
안정성과 입력 순서의 확정성 구분
안정 정렬은 같은 정렬 키를 가진 항목들의 기존 상대 순서를 보존한다. 정렬 키는 비교할 기준이며 안정성은 그 기준에서 동률인 항목을 어떻게 다루는지에 관한 성질이다.

동률 항목을 다루기

세 요청이 접수 순서대로 A, B, C이며 우선순위가 각각 2, 1, 2라고 하자. 우선순위 오름차순으로 안정 정렬하면 B 뒤에 A와 C가 원래의 상대 순서로 놓인다. 안정성이 없으면 A와 C의 순서는 별도 보장이 없을 수 있다. 무엇을 같은 키로 판단하는지가 안정성을 읽는 기준이다.

키와 항목 전체의 차이

사용자 자료를 이름으로 정렬할 때 항목에는 이름 외에도 여러 값이 있을 수 있다. 키가 이름이라면 그 기준의 동률과 항목 전체가 완전히 같다는 사실은 다르다. 문자열의 대소문자나 정규화 처리를 키에 반영했다면 무엇을 동률로 취급할지도 달라진다. 화면에 보이는 값과 실제 비교 기준을 함께 확인한다.

여러 기준의 우선순위

부서를 먼저 보고 같은 부서 안에서는 접수 시각을 보려면 우선 기준과 보조 기준을 명확히 정한다. 복합 키를 쓰거나 안정 정렬을 적절한 순서로 여러 번 적용하는 방법을 생각할 수 있다. 여러 번 정렬할 때는 보조 기준부터 적용하고 마지막에 우선 기준을 적용하는 원리를 이해해야 한다. 순서를 바꾸면 다른 결과를 만들 수 있다.

입력 순서가 바뀌는 경우

안정 정렬은 입력의 동률 순서를 보존하지만 입력 순서 자체를 항상 같게 만들어 주지는 않는다. 자료를 읽을 때마다 동률 항목의 순서가 달라진다면 안정 정렬 후에도 결과가 바뀔 수 있다. 페이지 구분이나 반복 조회에서 확정적인 순서가 필요하다면 추가 키를 명시하는 방식을 검토한다. 안정성과 완전한 정렬 기준은 다른 요구다.

검증할 사례

모든 키가 다른 자료만으로는 안정성 관련 요구를 확인하기 어렵다. 같은 키를 가진 여러 항목에 구분 가능한 식별자를 넣고 상대 순서를 점검한다. 결측값이나 비교할 수 없는 타입이 들어올 때의 규칙도 정한다. 정렬을 성공시켰는지뿐 아니라 제품에서 의도한 동률 처리와 일치하는지 확인해야 한다.

관련 문서

알고리즘 / 이진 탐색 / 데이터베이스