정렬의 안정적 특성
정렬되지 않은 상태에서 같은 key 값을 가진 원소의 순서가 정렬 후에도 유지되느냐에 관한 특성이다.
정렬의 안정적 특성에 따라
안정정렬, 불안정 정렬로 구분 가능
안정정렬
정렬 후에도 배열의 중복된 부분의 원래 순서가 유지된다
대표적으로 삽입정렬, 병합정렬, 버블정렬이 있다.
정렬 전
정렬 후
하트4 와 스페이스 4의 순서가 정렬 전,후에 유지된다.
즉, 하트4가 스페이스 4보다 앞에 있다는 특징이 유지된다.
다른 예시
정렬 전
[(대구, 1400), (순천, 1500), (대구, 1430), (부산, 1300), (목포, 1400), (대구, 1500)]
정렬 후
[(대구, 1400), (대구, 1430), (대구, 1500), (목포, 1400), (부산, 1300), (순천, 1500)]
대구의 중복된 데이터 3개의 시간 순서가 그대로 유지된다.
불안정정렬
정렬 후에 중복된 부분의 원래 순서가 유지된다는 보장이 없다.
대표적으로 퀵정렬, 선택정렬, 계수정렬이 있다.
정렬 전
정렬 후
하트4 와 스페이스4의 순서가 바뀌었다
