■ 히프 정렬 (Heap Sort)
1. 히프(heap) 자료구조를 사용하는 정렬 알고리즘임.
2. 히프는 최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조이며 완전 이진 트리이다.
3. 최대힙 혹은 최소 힙에서 삽입, 삭제 연산에 내포되어있는 정렬 알고리즘들이 히프 정렬이다.
* 완전이진트리 : 루트로부터 자식노드가 두 개씩 있는데 마지막 레벨의 노드들이 왼쪽부터 오른쪽으로 채워져있는 트리
(※ 마지막 바로 위 레벨 노드들은 다 꽉채워져있고 마지막 레벨의 노드들도 빈틈 없이 왼쪽부터 오른쪽 순서대로 채워져있어야함)
[히프 정렬 과정]
1. 정렬할 데이터들을 먼저 히프로 삽입해야 함
2. 그런 다음 루트 노드들 하나씩 삭제하여 꺼내면 히프에 있는 데이터들이 순서대로 나오게 되는데 이 순서대로 나열한 것이 히프 정렬
3. 오름차순 정렬을 하기 위해서는 최소 히프를 사용하고, 내림차순 정렬을 하기 위해서는 최대 히프를 사용
■ 최대 히프 (Max Heap)
⋅ 모든 노드의 키값이 자식노드의 키값보다 항상 크거나 같은 히프
⋅ 최대 히프의 루트노드는 모든 노드중 가장 큰 값이 위치
[클래스 구현]
[삽입 알고리즘]
Insert 이후 While문 안에서 다시 정렬하는 것을 볼 수 있다.
[삭제 알고리즘]
1. 최대 히프에선 루트 노드가 최댓값을 가지므로 루트 노드를 삭제하고 히프의 성질을 계속 유지하기 위해 히프를 재구성해야 함
2. 루트 노드가 삭제되면 히프의 전체 원소가 하나 줄어들게 되는데 이때 빈 루트 노드 자리에 히프의 마지막 노드를 가져옴. 이후 최대 히프의 형태를 띄우기 위해 정렬을 시작함
3. 이와 같이 루트 노드를 삭제하는 과정을 반복하게 되면 데이터들이 순서대로 나오게 되고 이것이 히프 정렬이 됨.
[사용]
■ 최소 히프 (Min Heap)
⋅ 모든 노드의 키값이 자식노드의 키값보다 항상 작거나 같은 히프
⋅ 최소 히프의 루트노드는 모든 노드 중 가장 작은 값이 위치
[클래스 구현]
MaxHeap과 대부분 동일. Insert와 Extract 메서드의 내용이 다름
[삽입 알고리즘]
[삭제 알고리즘]
[사용]
■ 기수 정렬 (Radix Sort)
정렬한 원소의 키값을 나타내는 숫자의 자릿수(Radix) [10의 자리, 100의 자리, .. ]를 기초로 정렬하는 방법
* 키값의 최하위 자리인 가장 작은 자리수(Least Significant Digit)부터 최상위 자리수(Most Significant Digit)까지 차례로 한자리씩 정렬해 감 (ex. 537이면 1의자리인 7부터 100의자리인 5까지 한자리씩 정렬하는 것)
* 자리수가 고정되어 있으므로 데이터들 간의 상대적인 순서가 보존되는 안정적 정렬에 해당
[기수정렬 효율성]
1. 키값이 m자리 숫자인 경우 버킷에 분배 과정을 m번 반복
2. 비교 연산을 하지 않으며 전체 시간 복잡도는 O(dn)
(d: 데이터의 자릿수를 나타내며 대부분 d < 10 이하)
3. 제한적인 범위 내에 있는 숫자에 대해서 각 자릿수별로 정렬하므로 정수와 같은 자료를 정렬하는 경우 다른 비교 정렬 알고리즘들보다 빠름
4. 정렬 방법의 특수성 때문에 실수나 한글, 한자와 같은 문자열 등은 정렬이 불가능하며 정렬할 수 있는 데이터의 종류가 한정되어 있음
* 요약하자면 엄청 빠르고 좋지만 특정 자료형에만 사용이 가능하다는 단점이 있다.
[예시]
만약 십의 자리, 백의 자리 숫자라면 이 과정을 exponent(지수) 단위 별로 실행해준다.
일의 자리를 기준으로 정렬 후 십의 자리 기준으로 정렬 그 다음 백의 자리 수 기준으로 정렬. 이런식으로
* 코드는 계수 정렬과 함께 작성하여 활용하는 식으로 작성했다. 맨 아래 기재 예정
■ 계수 정렬 (Count Sort)
데이터들을 비교하지 않고 데이터가 등장한 횟수를 세서 그 기준으로 정렬하는 방법
[특징]
· 데이터의 출현 빈도를 기준으로 정렬
· 정렬 대상인 데이터에서 같은 키값의 개수를 계산하고 특정 키값보다 작은 키값이 몇 개인가를 계산하여 그 데이터의 위치를 결정
· 계수 정렬은 선형 시간[ O(n) ]에 정렬하는 효율적인 알고리즘
[예시]
[더 효율적인 방식의 계수 정렬]
배열 Count의 각 인덱스에 해당하는 값을 이전 인덱스의 값과 누적하여 새로운 배열 Count'를 작성하는 것이다.
그 이후 배열 Array의 맨 뒤에서 부터 값을 읽어오는데 맨 뒤에 Array[6]에는 4가 있다.
4에 해당하는 배열 Count'의 값을 확인 .Count'[4]은 5가 있음을 알 수 있다.
이는 정렬된 결과 배열 (Sorted)의 다섯번째 값에 4를 저장하라는 의미이다.
따라서 Sorted[5]에 4가 저장이 되고 Count'[4]의 숫자를 하나 줄여준다.
이를 반복하면 정렬된 숫자를 얻게 된다.
[계수 정렬의 효율성]
1. 같은 키값을 갖는 데이터가 여러 개일 때 효과적
2. O(n)의 빠른 시간 복잡도
3. 계수 정렬은 정렬을 하기 위해 길이 n의 배열 하나와 계수를 위한 길이 k의 배열 하나가 필요
4. 따라서 O(n+k)의 공간 복잡도를 가짐
■ 기수 정렬 & 계수 정렬 구현
[Main]
[기수 정렬 (Radix Sort)]
[계수 정렬 (Count Sort)]
[왜 혼용해서 사용했나?]
기수 정렬(Radix Sort)은 종종 다른 정렬 알고리즘과 함께 사용되거나 복합적인 문제 해결에 활용될 수 있다.
하지만 기수 정렬만을 단독으로 사용하는 경우는 그다지 흔하지 않다.
이는 기수 정렬이 주로 정수나 문자열과 같은 특정한 데이터 형식에 적합하며, 범용적인 정렬 문제에 대한 해결책으로는 충분하지 않기 때문이다.
■ 정렬 알고리즘 성능 비교
| 알고리즘 | 최선의 경우 | 평균적인 경우 | 최악의 경우 |
| 선택 정렬 | O(n^2) | O(n^2) | O(n^2) |
| 버블 정렬 | O(n^2) | O(n^2) | O(n^2) |
| 삽입 정렬 | O(n) | O(n^2) | O(n^2) |
| 셀 정렬 | O(n) | O(n^1.5) | O(n^1.5) |
| 퀵 정렬 | O(nlogn) | O(nlogn) | O(n^2) |
| 병합 정렬 | O(nlogn) | O(nlogn) | O(nlogn) |
| 히프 정렬 | O(nlogn) | O(nlogn) | O(nlogn) |
| 기수 정렬 | O(dn) | O(dn) | O(dn) |
'Computer Science > Algorithm' 카테고리의 다른 글
| [Algorithm] 다익스트라(Dijikstra) 알고리즘 (2) | 2024.03.25 |
|---|---|
| [Algorithm] BFS, DFS (0) | 2024.03.25 |
| [Algorithm] 셸, 병합, 퀵 정렬 (0) | 2024.02.07 |
| [Algorithm] 선택 정렬, 버블 정렬, 삽입 정렬 (1) | 2024.02.07 |
| [Algorithm] 정렬 알고리즘,내부정렬, 외부정렬 (0) | 2024.02.07 |
