· 개발

안정 정렬(stable sort)이란: 같은 값의 순서가 지켜지는 정렬

안정 정렬의 뜻, 여러 기준으로 정렬할 때 왜 중요한지, Python·JavaScript·Java·C++ 표준 정렬이 무엇을 보장하는지 명세와 공식 문서를 기준으로 정리했습니다.

개발알고리즘

표에서 “날짜” 열을 눌러 정렬했더니 같은 날짜의 행끼리 순서가 뒤섞인 적이 있다면, 그건 버그가 아닐 수도 있습니다. 정렬 알고리즘이 안정(stable) 한지 아닌지의 차이입니다.

안정 정렬의 뜻

정렬 기준으로 비교했을 때 같은 값인 원소들이, 정렬 뒤에도 원래의 상대 순서를 유지하면 안정 정렬입니다. Python 문서의 표현을 빌리면 “같은 키를 가진 레코드가 여럿일 때 원래 순서가 보존된다”는 뜻입니다.

주문 목록을 날짜로 정렬하는 예를 보겠습니다.

원래 순서 주문 날짜
1 A 9월 2일
2 B 9월 1일
3 C 9월 2일

날짜로 정렬하면 B가 맨 앞에 옵니다. 안정 정렬이라면 그다음은 반드시 A, C 순서입니다. 불안정 정렬이라면 C, A가 될 수도 있습니다. 둘 다 “날짜순”이라는 조건은 만족하므로 틀린 결과는 아니지만, 같은 날짜 안의 순서는 보장되지 않습니다.

숫자 하나짜리 배열처럼 같은 값끼리 구별할 방법이 없으면 안정성은 의미가 없습니다. 레코드나 객체처럼 정렬 키 말고도 다른 정보가 붙어 있을 때 차이가 드러납니다.

왜 중요한가: 여러 기준으로 정렬하기

안정 정렬의 가장 실용적인 쓰임은 여러 번 나눠서 정렬하는 것입니다. “부서별로, 같은 부서 안에서는 급여 등급별로” 정렬하고 싶다면 보조 기준으로 먼저 정렬하고, 주 기준으로 나중에 정렬하면 됩니다. 두 번째 정렬이 안정적이라서 같은 부서 안에서는 첫 번째 정렬의 결과가 그대로 남습니다.

Python 공식 문서도 이 방법을 소개합니다.

from operator import attrgetter

s = sorted(students, key=attrgetter("age"))            # 보조 기준: 나이
s = sorted(s, key=attrgetter("grade"), reverse=True)   # 주 기준: 학년(내림차순)

표 UI에서 사용자가 열 머리글을 차례로 누를 때 앞서 누른 열의 순서가 동점 구간 안에 남는 것도 같은 원리입니다. 정렬이 불안정하면 이 동작을 기대할 수 없습니다.

언어별 표준 정렬이 보장하는 것

“대부분 안정적이던데”가 아니라 명세나 문서가 보장하는지를 봐야 합니다. 구현이 우연히 안정적이어도 명세가 보장하지 않으면 버전이나 환경에 따라 달라질 수 있습니다.

언어 함수 안정성
Python list.sort(), sorted() 보장. 공식 문서에 “guaranteed to be stable”로 명시
JavaScript Array.prototype.sort() ECMAScript 2019(10판)부터 명세상 보장. 단, 비교 함수가 일관적일 때만(아래 참고). 그 이전 명세는 보장하지 않았음
Java Arrays.sort(Object[]), List.sort() 보장. “equal elements will not be reordered”
Java Arrays.sort(int[]) 등 기본형 안정성 언급 없음. 구현은 Dual-Pivot Quicksort이지만, 같은 int 값끼리는 구별할 수 없어 문제가 되지 않음
C++ std::sort 보장하지 않음. 표준은 std::stable_sort에만 안정적(Stable)이라고 적고 std::sort에는 그런 조건이 없음
C++ std::stable_sort 보장. 대신 추가 메모리가 부족하면 비교 횟수가 N·log²N 정도까지 늘어남

Python의 정렬은 Timsort이고, Java의 List.sort() 구현도 Python의 Timsort를 가져와 만든 안정 병합 정렬이라고 문서에 적혀 있습니다.

JavaScript: 안정성은 비교 함수가 제대로일 때만

ECMAScript 명세(ECMA-262)가 Array.prototype.sort의 안정성을 요구하는 것은 비교 함수가 일관적인 비교 함수(consistent comparator) 일 때뿐입니다. 그렇지 않으면 정렬 순서는 구현이 정합니다(implementation-defined). 즉 안정성은커녕 결과가 정렬되어 있다는 보장도 없습니다.

비교 함수 (a, b) => …는 숫자를 돌려줘야 하고, 그 부호로 뜻이 정해집니다.

  • 음수: a가 b보다 앞
  • 양수: a가 b보다 뒤
  • 0: 둘은 같음(안정 정렬이면 원래 순서 유지)

흔한 실수는 비교 결과를 불리언으로 돌려주는 것입니다.

players.sort((a, b) => a.score > b.score);   // 잘못된 비교 함수
players.sort((a, b) => a.score - b.score);   // 올바른 비교 함수(오름차순)

명세는 비교 함수의 반환값을 숫자로 바꾸므로 true는 1, false는 0이 됩니다. a.score < b.score일 때 음수가 나와야 하는데 0이 나오니 “같다”는 뜻이 되고, 인자 순서를 바꿔 부르면 1이 나와 “다르다”가 됩니다. 이런 함수는 일관적인 비교 함수가 아니어서, 어떤 엔진에서는 우연히 맞게 정렬되더라도 명세상 결과를 믿을 수 없습니다.

비교 함수를 아예 넘기지 않으면 기본 정렬은 값을 문자열로 바꿔서 비교합니다(undefined는 맨 뒤로 갑니다). 그래서 숫자 배열도 사전순이 됩니다.

[10, 9, 1].sort();                 // [1, 10, 9]
[10, 9, 1].sort((a, b) => a - b);  // [1, 9, 10]

안정성에 기대지 않는 방법

불안정한 정렬을 써야 하거나, 코드를 읽는 사람이 안정성을 몰라도 되게 하고 싶다면 비교 기준에 동점을 깨는 키를 넣는 방법이 있습니다. 예를 들어 날짜가 같으면 주문 번호로 비교하게 하면, 어떤 정렬 알고리즘을 써도 결과가 하나로 정해집니다.

orders.sort((a, b) => a.date.localeCompare(b.date) || a.id - b.id);

C++에서 std::sort에 이렇게 완전한 기준을 주면 std::stable_sort 없이도 결정적인 결과를 얻습니다. 반대로 “원래 입력 순서” 자체가 의미 있는 기준이고 따로 저장된 값이 없다면, 안정 정렬을 쓰는 것이 가장 간단합니다.

참고한 명세와 문서

블로그로