[정렬 알고리즘] #1. 안정 정렬 (Stable Sort) VS 불안정 정렬 (Unstable Sort)

안정 정렬 (Stable Sort)

안정 정렬이란 중복된 값들이 정렬한 후에도 입력된 순서와 동일하게 유지되는 특성을 말한다.

다음과 같은 카드 배치에서 숫자가 오름차순이 되게 정렬하고자 할 때 중복되는 숫자 7 카드들은 정렬되기 전의 순서가 그대로 유지된 채로 정렬이 완료된다. (하트 -> 스페이드 -> 다이아몬드 순서가 유지된다.)

대표적인 안정 정렬 알고리즘에는 버블 정렬, 삽입 정렬, 병합 정렬이 있다.

불안정 정렬 (Unstable Sort)

불안정 정렬이란 중복된 값들이 정렬한 후에 입력된 순서와 상관없이 무작위로 정렬이 되는 특성을 말한다.

다음과 같은 카드 배치에서 숫자가 오름차순이 되게 정렬하고자 할 때 중복되는 숫자 7 카드들은 정렬되기 전의 순서가 유지되지 않고 무작위로 섞이게 된다.

대표적인 불안정 정렬 알고리즘에는 선택 정렬, 퀵 정렬, 계수 정렬이 있다.