안정 정렬(Stable Sort)이란 무엇인가요?

안정 정렬(Stable Sort)은 정렬 기준이 같은 원소들의 상대적 순서를 정렬 후에도 유지하는 정렬입니다. 여러 기준으로 단계적으로 정렬하거나, 원본 순서가 의미를 가질 때 중요합니다.

핵심 개념

• 같은 key를 가진 A와 B가 원래 A, B 순서였다면 정렬 후에도 A, B 순서가 유지됩니다.
• 안정 정렬을 이용하면 보조 기준부터 먼저 정렬하고 주 기준을 나중에 정렬하는 방식이 가능합니다.
• Merge Sort, Insertion Sort는 안정적으로 구현하기 쉽고, Quick Sort/Heap Sort는 일반적으로 불안정합니다.

동작 방식 또는 판단 기준

이 주제를 이해할 때는 다음 순서로 보면 실무 적용이 쉬워집니다.

1. 무엇을 해결하려는가: 성능, 표현력, 안정성, 접근성 중 어떤 문제를 줄이려는지 확인합니다.
2. 전제 조건은 무엇인가: 정렬 여부, 브라우저 지원, 네트워크 특성, 동시성 조건처럼 성립해야 하는 조건을 점검합니다.
3. 비용은 어디서 발생하는가: 시간 복잡도, 메모리, 캐시, 재시도, 렌더링 비용처럼 병목 지점을 나눠 봅니다.
4. 실패 시 어떤 문제가 생기는가: 잘못 적용했을 때의 버그나 운영 리스크를 함께 고려합니다.

실제 예시

원본:
1. Kim  score=90  joined=1
2. Lee  score=80  joined=2
3. Park score=90  joined=3

score 내림차순 안정 정렬:
Kim(90) -> Park(90) -> Lee(80)
동점인 Kim/Park의 원래 순서 유지

const users = [
  { name: 'Kim', team: 'A', score: 90 },
  { name: 'Lee', team: 'B', score: 90 },
];
users.sort((a, b) => b.score - a.score); // 최신 JS 엔진의 Array.prototype.sort는 안정 정렬

실무에서 주의할 점

• 언어/버전별 sort 안정성 보장이 다를 수 있으므로 문서를 확인해야 합니다.
• 비교 함수가 일관되지 않으면 안정 정렬이어도 결과가 예측 불가능합니다.
• 안정성이 필요 없는 곳에서만 성능이나 메모리 기준으로 다른 정렬을 선택할 수 있습니다.

실무 적용 가이드

• UI 목록에서 같은 점수/날짜 항목의 기존 순서를 유지해야 하면 안정 정렬이 중요합니다.
• 다중 정렬은 하나의 comparator로 명시하거나, 안정 정렬을 전제로 보조 기준부터 적용합니다.
• 정렬 기준이 같을 때는 id 같은 tie-breaker를 넣어 결과를 더 결정적으로 만들 수 있습니다.

함께 연결해서 보면 좋은 키워드

Stable Sort, Sorting, Comparator, Tie-breaker

정리

안정 정렬(Stable Sort)은 정렬 기준이 같은 원소들의 상대적 순서를 정렬 후에도 유지하는 정렬입니다. 다만 개념 자체보다 중요한 것은 적용 조건과 한계를 함께 이해하는 것입니다. 작은 예제에서는 단순해 보여도 실제 서비스에서는 성능, 보안, 유지보수성, 접근성 요구사항이 함께 얽히므로, 문제의 성격을 먼저 파악한 뒤 적절한 도구로 선택하는 것이 좋습니다.