안정 정렬 vs 불안정 정렬 (Sort Stability)

안정 정렬 vs 불안정 정렬 (Sort Stability)

동일 키를 가진 원소들의 상대적 순서가 정렬 후에도 유지되는지 여부에 따라 안정(Stable) 정렬과 불안정(Unstable) 정렬로 구분

목적: 다중 키 정렬 시 이전 정렬 결과 보존, 데이터 무결성 보장

중요성: 다중 키 정렬(예: 이름순 정렬 후 나이순 정렬 시 같은 나이의 이름 순서 유지), 데이터베이스 ORDER BY

안정 정렬: 동일 키 원소의 입력 순서가 출력에서도 유지

• •병합 정렬(Merge Sort): O(n log n), 추가 메모리 O(n)
• •삽입 정렬(Insertion Sort): O(n²), 제자리
• •버블 정렬(Bubble Sort): O(n²), 제자리
• •계수 정렬(Counting Sort): O(n+k), 비비교
• •팀 정렬(TimSort): O(n log n), 하이브리드

불안정 정렬: 동일 키 원소의 상대 순서 보장 없음

• •퀵 정렬(Quick Sort): O(n log n) 평균, 제자리
• •힙 정렬(Heap Sort): O(n log n), 제자리
• •선택 정렬(Selection Sort): O(n²), 제자리
• •셸 정렬(Shell Sort): O(n^1.5), 제자리

비교 표

연관: 정렬 알고리즘, 병합 정렬, 퀵 정렬, 팀 정렬, 다중 키 정렬