Stable Sort

Concept

키 값이 같은 원소 간의 순서가 정렬 후에도 유지된다. 즉, 정렬 시 같은 값이 있다면, 앞에 있었던 건 앞에 뒤에 있었던건 뒤에 위치시킨다는 이야기 이다.

반대로 이 순서를 보장하지 않는다면 그건 unstable sort라고 부른다.

Detail

다음과 같은 다섯명의 성적을 시험 점수를 기준으로 내림차순 정렬한다고 하자

• A, 85
• B, 90
• C, 55
• D, 85
• E, 68

stable sort 결과는 B(90)-A(85)-D(85)-E(68)-C(55)로 A가 D보다 앞에 나온 다는 것이 보장한다.
하지만 unstable sort에서는 A와 C중 어느 것이 앞에 나올지 알 수 없다.

마치며

개발 하다보면, 정렬 후 키가 중복일 경우 순서가 유지될거라는 당연한생각을 하게 될 수 있다. 테스트 시 이부분은 놓치기 쉽다.
본인이 어떤 정렬을 하는지 알고, 그 정렬이 stable 여부를 판단할 줄 안다면, production env에서의 장애는 막을 수 있을 거 같다.