[자료구조] Stable Sort, Unstable Sort (안정 정렬, 불안정 정렬)

안정 정렬

알고리즘은 반복되는 요소를 입력 때와 동일한 순서로 정렬

불안정 정렬

알고리즘은 반복되는 요소를 입력 때와 동일한 순서로 정렬을 보장하지 못함

https://ko.wikipedia.org/wiki/%EC%A0%95%EB%A0%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

위의 그림에서 처럼 중복되는 값이 있을 경우 안정정렬은 정렬 후에도 중복된 값들이 이전 정렬의 순서를 유지합니다.
그에 반해 불안정 정렬은 중복된 값들이 이전 정렬의 순서가 유지 되지 않을 수 있습니다.

대표적인 정렬

삽입 정렬 - 안정
버블 정렬 - 안정
합병 정렬 - 안정

선택 정렬 - 불안정
퀵 정렬 - 불안정
힙 정렬 - 불안정