정렬 (Sorting)

정렬 (Sorting)

데이터를 특정 순서(오름차순/내림차순)로 재배열하는 알고리즘

목적: 검색 효율, 데이터 조직, 전처리, 중복 제거

특징: 비교 기반/비비교 기반, 안정/불안정, 제자리/외부

안정 정렬(Stable): 같은 값의 상대적 순서 유지, 버블/삽입/병합

불안정 정렬(Unstable): 순서 보장 안함, 선택/퀵/힙

제자리 정렬(In-place): O(1) 추가 공간, 버블/삽입/선택/퀵

비교 기반 정렬: 하한 Ω(n log n), 병합/퀵/힙

비비교 기반 정렬: O(n) 가능, 계수/기수/버킷

주요 알고리즘: 버블, 선택, 삽입, 병합, 퀵, 힙, 계수, 기수

정렬 알고리즘 종합 비교표

적용사례: 데이터 정렬, 검색 전처리, 순위, 중복 제거

연관: 버블 정렬, 병합 정렬, 퀵 정렬, 힙 정렬, 시간 복잡도