[자료구조] 25. 정렬 알고리즘 (3)

1. 힙 정렬

개념 설명

• 힙 정렬(Heapsort)은 **힙(Heap)**이라는 특수한 자료구조를 활용하는 정렬 알고리즘이다.

• 최대 힙(Max Heap): 원소를 반복적으로 삭제하면 내림차순 정렬

• 최소 힙(Min Heap): 원소를 반복적으로 삭제하면 오름차순 정렬

 

힙의 특징

• 완전 이진 트리 구조

• 우선순위 큐(Priority Queue)로도 사용됨

• 부모 노드와 자식 노드 간에는 다음과 같은 관계가 성립함

- 최대 힙: 부모 ≥ 자식
- 최소 힙: 부모 ≤ 자식

→ 루트 노드에 항상 최댓값(또는 최솟값)이 위치함

 

복잡도 분석

• 메모리 사용: n개의 힙 구성 시 n개의 메모리 공간 필요

• 힙 구성 시간: O(log₂n)

• 전체 n개의 노드에 대해 O(n log₂n)의 정렬 시간 소요

• 시간 복잡도 (최선/평균/최악): 모두 O(n log₂n)

 

 

2. 선택 정렬

개념 설명

• 선택 정렬(Selection Sort)은 가장 작은(또는 큰) 값을 선택하여 해당 위치의 데이터와 교환하는 방식으로 정렬을 수행한다.

• 정렬되지 않은 리스트에서 최솟값을 선택하여 맨 앞의 값과 교환

• 반복하며 왼쪽 리스트는 정렬된 상태, 오른쪽 리스트는 아직 정렬되지 않은 상태로 유지됨

 

복잡도 분석

• 비교 횟수: (n - 1) + (n - 2) + ... + 1 = n(n - 1)/2 → O(n²)

• 이동 횟수: 3(n - 1)

• 전체 시간 복잡도: O(n²)

 

 

3. 기수 정렬

개념 설명

• 기수 정렬(Radix Sort)은 데이터를 비교하지 않고 자릿수를 기준으로 정렬을 수행하는 방식이다.

• 정수형 데이터나 고정 길이의 문자열에 효과적

• 자릿수(d)를 기준으로 가장 낮은 자리부터 차례로 정렬을 반복 수행

 

복잡도 분석

• 시간 복잡도: O(dn) (d: 자릿수, n: 레코드 수)

• 일반적으로 d < 10이므로 매우 빠른 정렬 가능

• 단점: 실수형, 한글, 한자 등의 키값은 정렬 어려움

 

 

4. 정렬 알고리즘 비교 표

알고리즘	최선	평균	최악
삽입 정렬	O(n)	O(n²)	O(n²)
선택 정렬	O(n²)	O(n²)	O(n²)
버블 정렬	O(n²)	O(n²)	O(n²)
쉘 정렬	O(n)	O(n^1.5)	O(n^1.5)
퀵 정렬	O(n log n)	O(n log n)	O(n²)
힙 정렬	O(n log n)	O(n log n)	O(n log n)
병합 정렬	O(n log n)	O(n log n)	O(n log n)
기수 정렬	O(dn)	O(dn)	O(dn)

 

---

이 내용은 휴넷사회복지평생교육원의 자료구조 강의를 듣고 정리한 것입니다.