🧮 기본 소팅 알고리즘들(Time Complexity 비교 포함)

1. 정렬(Sorting)의 개요

• 자료를 일정한 기준에 따라 순서대로 나열하는 처리 과정
• 오름차순, 내림차순, 사용자 정의 기준 등 다양한 정렬 기준 존재
• 자료의 검색, 통계, 시각화, 데이터 처리 속도 향상 등에 기여함
• 정렬 알고리즘은 비교 기반(Comparison-Based)과 비비교 기반(Non-Comparison-Based)으로 분류됨

---

2. 주요 정렬 알고리즘의 분류 및 특징

가. 버블 정렬 (Bubble Sort)

• 인접한 두 요소를 비교하여 큰 값을 뒤로 보내는 방식
• 매 반복마다 가장 큰 값이 끝으로 밀려나감
• 정렬이 완료될 때까지 전체 배열을 반복적으로 순회
• 구현이 단순하고 직관적이나, 성능이 매우 낮음
• 최악/평균/최선 모두 O(n²), 이미 정렬된 경우 O(n)으로 최적화 가능
• 실무 사용은 거의 없음, 교육용 또는 개념 설명용에 한정됨

나. 선택 정렬 (Selection Sort)

• 전체 자료에서 최소값을 찾아 맨 앞과 교환
• 정렬이 완료될 때까지 이 과정을 반복
• 교환 횟수가 적으나, 비교 횟수가 많음
• 시간 복잡도는 항상 O(n²)로 고정
• 데이터 이동 비용이 높은 경우에도 효율적이지 못함
• 안정 정렬이 아니며, 대규모 데이터에는 부적합함

다. 삽입 정렬 (Insertion Sort)

• 현재 위치의 데이터를 앞쪽 정렬된 영역에 삽입
• 정렬된 영역을 유지하면서 뒤쪽 데이터를 삽입하는 방식
• 최선의 경우(이미 정렬된 데이터)에는 O(n), 평균/최악은 O(n²)
• 소규모 데이터나 거의 정렬된 데이터에는 효과적임
• 안정 정렬이며, 구현도 간단

라. 병합 정렬 (Merge Sort)

• 분할 정복(Divide and Conquer) 기반의 알고리즘
• 리스트를 재귀적으로 반으로 나누고, 병합 시 정렬하여 합침
• 항상 O(n log n)의 성능 유지, 최악의 경우에도 동일
• 안정 정렬이며, 대용량 데이터 처리에 유리
• 단점은 추가 메모리 공간 필요 (O(n))

마. 퀵 정렬 (Quick Sort)

• 분할 정복 기반, 피벗(Pivot)을 기준으로 좌우를 재귀적으로 정렬
• 평균 O(n log n), 최악의 경우 O(n²) 발생 가능 (피벗 선택에 따라 달라짐)
• 불안정 정렬이나, 실제 환경에서 매우 빠른 성능 보임
• 내부 정렬(in-place sorting)로 메모리 효율적
• 대부분의 언어에서 기본 정렬 알고리즘으로 채택됨

바. 힙 정렬 (Heap Sort)

• 최대 힙(Max Heap) 또는 최소 힙(Min Heap)을 기반으로 정렬 수행
• 트리 구조를 배열 형태로 구성하여 정렬
• 시간 복잡도는 항상 O(n log n), 불안정 정렬
• 추가 메모리 없이 동작 가능하며, 실시간 처리에 적합
• 삽입, 삭제가 빈번한 데이터 구조에는 부적합

사. 기수 정렬 (Radix Sort)

• 자리수별로 데이터를 분류하며 정렬
• 비비교 기반 알고리즘, 정수형 데이터에 최적화
• 시간 복잡도는 O(nk) (n: 데이터 수, k: 자리수)
• 안정 정렬, 비교 기반보다 빠를 수 있음
• 데이터 유형 및 범위 제한 존재 (정수, 고정 자리수 등)

---

3. 정렬 알고리즘별 시간복잡도 비교

알고리즘	최선 시간	평균 시간	최악 시간	공간 복잡도	안정성
버블 정렬	O(n)	O(n²)	O(n²)	O(1)	○
선택 정렬	O(n²)	O(n²)	O(n²)	O(1)	×
삽입 정렬	O(n)	O(n²)	O(n²)	O(1)	○
병합 정렬	O(n log n)	O(n log n)	O(n log n)	O(n)	○
퀵 정렬	O(n log n)	O(n log n)	O(n²)	O(log n)	×
힙 정렬	O(n log n)	O(n log n)	O(n log n)	O(1)	×
기수 정렬	O(nk)	O(nk)	O(nk)	O(n + k)	○

---

4. 실제 적용 시 고려사항

• 데이터 크기: 대용량 데이터에는 O(n log n) 이상의 성능이 요구됨
• 메모리 제약: 병합 정렬은 추가 공간 필요, 퀵 정렬은 공간 효율 우수
• 안정성 필요 여부: 키 중복 발생 시 안정 정렬 필요
• 데이터 형태: 정수 중심이면 기수 정렬 고려, 실수/문자열이면 비교 기반 우위
• 정렬 빈도: 반복 정렬 필요한 경우, 삽입 정렬 등 단순 알고리즘도 유효

---

5. 결론

• 정렬 알고리즘은 상황에 따라 선택적으로 적용하는 것이 핵심
• 이론적 복잡도뿐 아니라 실제 환경에서의 성능, 구현 난이도, 데이터 특성 고려 필요
• 최신 프로그래밍 언어/라이브러리들은 퀵 정렬 + 병합 정렬을 혼합한 하이브리드 방식 채택
• 정렬은 검색, 군집화, 시각화 등 다양한 데이터 처리의 기반 요소로서 중요한 역할 수행

---