안정 정렬 vs 불안정 정렬

KTX 역에서 도착역과 출발 시간으로 이루어진 다음과 같은 데이터가 있다고 가정해 봅시다.

[(대구, 1400), (순천, 1500), (대구, 1430), (부산, 1300), (목포, 1400), (대구, 1500)]

지역명으로 오름차순으로 정렬한다고 했을 때, 다음과 같이 우리는 '대구->목포->부산->순천' 순으로 정렬하면서 대구의 중복된 데이터 3개는 시간 순서대로 그대로 유지되게 하고 싶겠죠.

[(대구, 1400), (대구, 1430), (대구, 1500), (목포, 1400), (부산, 1300), (순천, 1500)]

하지만 정렬 방법마다 이렇게 중복된 원소가 본래 순서대로 정렬될 수도 있고 정렬되지 않고 섞일 수도 있습니다. 이번 포스트에서 살펴볼 내용은 안정정렬과 불안정정렬입니다.

안정 정렬 (Stable Sort)

안정정렬은 중복된 값을 입력 순서와 동일하게 정렬하는 정렬 알고리즘의 특성을 말합니다.

대표적으로 삽입정렬, 병합정렬, 버블정렬 이 있습니다. 각 알고리즘을 살펴보시면 중복된 부분은 순서가 유지되는 것을 알 수 있습니다.

불안정 정렬 (Unstable Sort)

불안정 정렬은 안정 정렬과 반대로 중복된 값이 입력 순서와 동일하지 않게 정렬되는 알고리즘을 말합니다.

대표적으로 퀵정렬, 선택정렬, 계수정렬 이 있습니다. 

홍머스 정리

• 입력 값이 유지되는 안정 정렬이 보통 더 유용하지 않을까...?