값이 같은 원소들이 정렬 후에도 원래 순서를 유지하면 안정 정렬, 순서가 뒤바뀔 수 있으면 불안정 정렬이다. 값만 놓고 보면 어느 쪽이든 결과가 똑같아서 왜 구분하나 싶지만, 두 번 정렬할 때 차이가 드러난다.
두 기준으로 차례로 정렬하기
로그 데이터가 시간순으로 정렬되어 있다고 하자. 이걸 다시 지역별로 정렬한다. 안정 정렬이면 같은 지역 안에서는 여전히 시간순이라 두 기준으로 정렬한 결과가 공짜로 나온다. 불안정 정렬이면 같은 지역 안의 시간 순서는 보장되지 않는다.
여러 기준으로 차례차례 정렬하는 방식이 안정 정렬에서만 성립하는 것이다. 중요한 기준을 나중에 정렬하면 된다.
같은 값의 원래 순서
카드 다섯 장을 숫자로 정렬한다고 하자. 하트 5와 스페이드 5가 있고 정렬 전에는 하트 5가 앞에 있었다. 안정 정렬이면 정렬 후에도 하트 5가 스페이드 5보다 앞이고, 불안정 정렬이면 스페이드 5가 앞에 올 수도 있다. 형식적으로는 키가 같은 (kᵢ, eᵢ)와 (kⱼ, eⱼ)에 대해 정렬 전 i < j였다면 정렬 후에도 i < j인 것이다.
교환 거리가 가르는 안정성
버블 정렬, 삽입 정렬, 합병 정렬이 안정이고 선택 정렬, 퀵 정렬, 힙 정렬이 불안정이다. 규칙성이 보인다. 이웃끼리만 자리를 바꾸는 정렬은 안정적이고, 멀리 떨어진 원소를 교환하는 정렬은 불안정하다. 멀리 있는 것과 바꾸는 순간 그 사이에 있던 같은 값과의 순서가 뒤집히기 때문이다.
자바 표준 라이브러리의 선택
자바는 같은 이름의 메서드가 인자 타입에 따라 다르게 동작한다.
Arrays.sort(int[])는 듀얼 피벗 퀵소트를 쓴다. 피벗을 두 개 잡아 세 구간으로 나누는 방식으로 비교 횟수를 줄이는데, 불안정하다. 기본형 배열은 값만 있고 신원이 없어서 안정성이 의미가 없으니 더 빠른 쪽을 택한 것이다.
Arrays.sort(Object[])와 Collections.sort()는 삽입 정렬과 합병 정렬을 섞은 팀소트를 쓰고, 안정하다. 객체는 같은 키를 가져도 서로 다른 개체라 순서가 의미를 갖기 때문이다.