[알고리즘] 9. 정렬 알고리즘 (3)

1. 힙 정렬 (Heap Sort)

1) 힙 정렬 개요

• 힙 자료구조를 이용한 정렬 알고리즘.

• 힙은 최댓값 또는 최솟값을 쉽게 추출할 수 있는 완전 이진 트리.

• 정렬할 데이터를 힙에 삽입한 후, 루트 노드를 반복적으로 삭제하여 정렬된 데이터를 얻는 방식.

• 힙의 노드는 유일한 키 값을 가짐.

• 힙의 종류:

- 최대 힙: 모든 노드의 키 값이 자식보다 크거나 같음. 루트 노드는 최댓값을 가짐.

- 최소 힙: 모든 노드의 키 값이 자식보다 작거나 같음. 루트 노드는 최솟값을 가짐.

 

• 오름차순 정렬은 최소 힙, 내림차순 정렬은 최대 힙을 사용.

 

2) 힙의 연산

삽입 연산

• 새로운 노드를 힙의 마지막에 삽입.

• 부모 노드와 비교하여 힙의 성질을 만족하도록 교환.

 

삭제 연산

• 루트 노드를 삭제한 후 마지막 노드를 루트로 이동.

• 자식 노드와 비교하여 힙의 성질을 유지하도록 재구성.

 

3) 최대 힙의 삽입 연산 예시

• 데이터 8 삽입:

- 8이 부모(4)보다 크므로 교환.

- 8이 부모(7)보다 크므로 교환.

- 부모(9)보다 작으므로 종료.

 

4) 힙에서의 부모와 자식 관계

• 왼쪽 자식 인덱스 = (부모 인덱스) * 2

• 오른쪽 자식 인덱스 = (부모 인덱스) * 2 + 1

• 부모 인덱스 = (자식 인덱스) / 2

 

5) 최대 힙의 삭제 연산 예시

• 루트(최댓값) 삭제 후 마지막 노드를 루트로 이동.

• 루트와 자식 노드 중 큰 값과 교환을 반복하여 힙 성질 유지.

 

6) 힙 정렬의 시간 복잡도

• 힙의 높이: log n

• 삽입 또는 삭제 연산의 시간: O(log n)

• 전체 정렬: O(n log n)

• 효율적인 정렬 알고리즘 중 하나.

 

 

 

2. 기수 정렬 (Radix Sort)

1) 기수 정렬 개요

• 데이터의 자릿수를 기준으로 정렬하는 방법.

• 최하위 자릿수부터 최상위 자릿수까지 차례로 정렬.

• 데이터의 상대적 순서를 유지하는 안정적 정렬.

 

2) 효율성

• 자릿수가 m이면 m번 버킷 분배 과정 반복.

• 비교 연산 없이 정렬 가능.

• 시간 복잡도: O(dn) (d: 자릿수, 일반적으로 d < 10).

• 정수 정렬에 효과적이나, 실수나 문자열 정렬은 불가능.

 

 

 

3. 계수 정렬 (Counting Sort)

1) 계수 정렬 개요

• 데이터의 등장 횟수를 세어 정렬하는 방법.

• 데이터의 출현 빈도를 기준으로 정렬.

• 비교 연산 없이 정렬 가능.

 

2) 계수 정렬 과정

• 카운트 배열 C를 생성하여 각 숫자의 등장 횟수를 저장.

• C 배열을 누적하여 데이터의 위치를 결정.

• 정렬된 결과를 새로운 배열 B에 저장.

 

3) 계수 정렬의 예시

• 배열 A의 원소들을 C 배열에 빈도수로 기록.

• 누적 합을 계산하여 C' 배열 생성.

• 뒤에서부터 A 배열의 원소를 읽어 C' 값을 참조해 B 배열에 저장.

• 저장할 때마다 C' 값을 감소시켜 위치 조정.

 

4) 계수 정렬의 효율성

• 동일한 키 값을 가지는 데이터 정렬에 효과적.

• 시간 복잡도: O(n).

• 공간 복잡도: O(n + k) (k: 데이터 범위 크기).

• 추가적인 배열이 필요하므로 공간 효율성이 낮을 수 있음.

---

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