목차
정렬
히프 정렬 Heap Sort
히프 정렬은 히프 자료구조를 이용하여 정렬하는 방법이다.
히프에서는 항상 가 장 큰 원소가 루트 노드가 되고. 삭제 연산을 수행하면 항상 루트 노드의 원소를 삭제하여 반환하는 특징이 있다. 그러므로 최대 히프에 대해서 원소 개수만큼 삭제 연산을 수행하면 내림차순으로 정렬된 원소를 얻을 수 있고, 최소 히프에 대해서 원소 개수만큼 삭제 연산을 수행하면 오름차순으로 정렬된 원소를 얻을 수 있다. 히프 정렬은 정렬할 원소들을 하나씩 히프에 삽입하여 정렬할 n개의 원소를 가진 최대 히프를 구성한다. 히프에 삭제 연산을 수행하여 얻은 루트 원소를 저장하고, 히프를 다시 최대 히프가 되도록 재구성하는 작업을 원소의 개수만큼 반복하면 정렬을 완성할 수 있다.
2023.11.20 - [알고리즘] - [알고리즘] 트리 6 - 히프 트리(Heap)
[알고리즘] 트리6 - 히프 트리(Heap)
ㅊ2023.11.14 - [알고리즘] - [알고리즘] 트리 5 - 균형 이진 탐색 트리(AVL) [알고리즘] 트리5 - 균형 이진 탐색 트리(AVL) 목차 2023.11.13 - [알고리즘] - [알고리즘] 트리 4 - 이진 탐색 트리 [알고리즘] 트리4
sun-dori.tistory.com
최대 히프 구성 (Max Heapify):
- 주어진 배열을 사용하여 초기에 최대 히프를 만든다.
- 배열의 중간부터 시작하여 왼쪽으로 이동하면서 각 노드에 대해 최대 히프 속성을 만족하도록 구성한다.
초기 배열: {69, 10, 30, 2, 16, 8, 31, 22}
list : { , , , , , , , }
1단계: {69, 10, 30, 2, 16, 8, 31, 2}
69
/ \
22 31
/ \ / \
16 10 8 30
/
2최대 히프에서 삭제 연산:
- 이제 최대 히프에서 삭제 연산을 실시하여 배열에 삽입한다.
삭제 연산 1번
초기 배열: {69, 10, 30, 2, 16, 8, 31, 22}
list : { , , , , , , , 69}
2단계: {69, 10, 30, 2, 16, 8, 31, 2}
31
/ \
22 30
/ \ / \
16 10 8 2삭제 연산 2번
초기 배열: {69, 10, 30, 2, 16, 8, 31, 22}
list : { , , , , , , 31, 69}
3단계: {69, 10, 30, 2, 16, 8, 31, 2}
30
/ \
22 8
/ \ /
16 10 2삭제 연산 3번
초기 배열: {69, 10, 30, 2, 16, 8, 31, 22}
list : { , , , , , 30, 31, 69}
4단계: {69, 10, 30, 2, 16, 8, 31, 2}
22
/ \
16 8
/ \
2 10삭제 연산 4번
초기 배열: {69, 10, 30, 2, 16, 8, 31, 22}
list : { , , , , 22, 30, 31, 69}
5단계: {69, 10, 30, 2, 16, 8, 31, 2}
16
/ \
10 8
/
2삭제 연산 5
초기 배열: {69, 10, 30, 2, 16, 8, 31, 22}
list : { , , , 16, 22, 30, 31, 69}
6단계: {69, 10, 30, 2, 16, 8, 31, 2}
10
/ \
2 8삭제 연산 6
초기 배열: {69, 10, 30, 2, 16, 8, 31, 22}
list : { , , 10, 16, 22, 30, 31, 69}
7단계: {69, 10, 30, 2, 16, 8, 31, 2}
8
/
2삭제 연산 7
초기 배열: {69, 10, 30, 2, 16, 8, 31, 22}
list : { , 8, 10, 16, 22, 30, 31, 69}
8단계: {69, 10, 30, 2, 16, 8, 31, 2}
2삭제 연산 8
초기 배열: {69, 10, 30, 2, 16, 8, 31, 22}
list : {2, 8, 10, 16, 22, 30, 31, 69} -> 정렬 완료
8단계: {69, 10, 30, 2, 16, 8, 31, 2}이렇게 정렬이 안료되는데...
히프 정렬은 n개의 원소에 대한 n개의 메모리와 n개의 노드로 구성된 히프를 저장할 공간이 추가로 필 요하다. 히프에 삭제 연산을 반복 수행하여 오름차순으로 정렬된 원소를 구하기 위해, 삭제 연산을 수행할 때마다 히프를 재구성하는 연산이 필요하다. 따라서 히프 정렬의 시간 복잡도는 히프의 재구성 시간으로 정해진다. n개의 노드에 대해 완전 이진트리는 log2(n+1) 레벨을 가지므로 완전 이진트리를 히프로 구성하는 평균 시간은 O(log2 n)이 된다. 따라서 n번 삭제 연산한 히프의 평균 재구성 시간은 O(nlog2 n)이 된다. 따라서 히프 정렬의 시간 복잡도는 O(nlog2n)이 된다.
트리 정렬 Tree Sort
트리 정렬은 이진 탐색 트리를 이용하여 정렬하는 방법이다. 정렬할 원소들은 이진 탐색 트리로 구성하고, 중위 우선 순회 방법을 사용하여 이진 탐색 트리의 원소들을 순회하는 경로가 오름차순 정렬이 된다.
2023.11.13 - [알고리즘] - [알고리즘] 트리 4 - 이진 탐색 트리
[알고리즘] 트리4 - 이진 탐색 트리
이진 탐색 트리 이진트리는 트리를 효율적으로 구현하고 관리하기 위해서 일정한 조건으로 정의한 것이며, 이진트리를 탐색용 자료구조로 사용하기 위해 원소 크기에 따라 노드 위치를 정해둔
sun-dori.tistory.com
이진 탐색 트리 구성:
- 주어진 배열 {69, 10, 30, 2, 16, 8, 31, 22}를 이진 탐색 트리에 삽입합니다.
- 초기 배열: {69, 10, 30, 2, 16, 8, 31, 22}
- 이진 탐색 트리 구성:
69
/
10
/ \
2 30
\ / \
8 16 31
\
22이진트리의 중위 순회(Inorder Traversal)는 다음과 같은 순서로 진행됩니다:
- L연산 -> 먼저 왼쪽 서브트리를 중위 순회합니다.
- D연산 -> 그다음 현재 노드를 방문합니다.
- R연산 -> 마지막으로 오른쪽 서브트리를 중위 순회합니다.
주어진 이진트리를 중위 순회하면 다음과 같다: 2 -> 8 -> 10 -> 16 -> 22 -> 30 -> 31 -> 69
#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct treeNode {
element key;
struct treeNode* left;
struct treeNode* right;
} treeNode;
// 이진 탐색 트리에서 키값이 x인 노드의 위치를 탐색하는 연산
treeNode* searchBST(treeNode* root, element x) {
treeNode* p;
p = root;
while (p != NULL) {
if (x < p->key) p = p->left;
else if (x == p->key) return p;
else p = p->right;
}
printf("\n 찾는 키가 없습니다!");
return p;
}
// 포인터 p가 가리키는 노드와 비교하여 노드 x를 삽입하는 연산
treeNode* insertBSTNode(treeNode* p, element x) {
treeNode* newNode;
if (p == NULL) {
newNode = (treeNode*)malloc(sizeof(treeNode));
newNode->key = x;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
else if (x < p->key) p->left = insertBSTNode(p->left, x);
else if (x > p->key) p->right = insertBSTNode(p->right, x);
else printf("\n 이미 같은 키가 있습니다! \n");
return p;
}
// 루트 노드부터 탐색하여 키값과 같은 노드를 찾아 삭제하는 연산
void deleteBSTNode(treeNode* root, element key) {
treeNode* parent, * p, * succ, * succ_parent;
treeNode* child;
parent = NULL;
p = root;
while ((p != NULL) && (p->key != key)) { // 삭제할 노드의 위치 탐색
parent = p;
if (key < p->key) p = p->left;
else p = p->right;
}
// 삭제할 노드가 없는 경우
if (p == NULL) {
printf("\n 찾는 키가 이진 트리에 없습니다!!");
return;
}
// 삭제할 노드가 단말 노드인 경우
if ((p->left == NULL) && (p->right == NULL)) {
if (parent != NULL) {
if (parent->left == p) parent->left = NULL;
else parent->right = NULL;
}
else root = NULL;
}
// 삭제할 노드가 자식 노드를 한 개 가진 경우
else if ((p->left == NULL) || (p->right == NULL)) {
if (p->left != NULL) child = p->left;
else child = p->right;
if (parent != NULL) {
if (parent->left == p) parent->left = child;
else parent->right = child;
}
else root = child;
}
// 삭제할 노드가 자식 노드를 두 개 가진 경우
else {
succ_parent = p;
succ = p->left;
while (succ->right != NULL) { // 왼쪽 서브 트리에서 후계자 찾기
succ_parent = succ;
succ = succ->right;
}
if (succ_parent->left == succ) succ_parent->left = succ->left;
else succ_parent->right = succ->left;
p->key = succ->key;
p = succ;
}
free(p);
}
// 이진 탐색 트리를 중위 순회하면서 출력하는 연산
void displayInorder(treeNode* root) {
if (root) {
displayInorder(root->left);
printf("%5d", root->key); //출력 형식 변경
displayInorder(root->right);
}
}
// 트리 정렬 연산
void treeSort(int a[], int n) {
treeNode* root = NULL; // 공백 이진 탐색 트리 생성
root = insertBSTNode(root, a[0]); // a[0]을 공백 이진 탐색 트리의 루트로 삽입
for (int i = 1; i < n; i++) // a[1]~a[n-1]의 원소들을
insertBSTNode(root, a[i]); // 삽입하면서 이진 탐색 트리 구성
displayInorder(root); // 이진 탐색 트리를 중위 순회한 경로 출력
}
int main(void) {
int i, list[8] = { 69, 10, 30, 2, 16, 8, 31, 22 };
int size = sizeof(list) / sizeof(list[0]); // list 배열의 원소 개수
printf("\n정렬할 원소 : ");
for (i = 0; i <= size - 1; i++) printf(" %d", list[i]);
printf("\n\n <<<<< 트리 정렬 수행 >>>>>> \n\n");
treeSort(list, size); // 트리 정렬 함수 호출
getchar(); return 0;
}
--------------------------------------------------
정렬할 원소 : 69 10 30 2 16 8 31 22
<<<<< 트리 정렬 수행 >>>>>>
2 8 10 16 22 30 31 69
'알고리즘' 카테고리의 다른 글
| [알고리즘] 검색 2 - 해싱 + 단어 사전 프로그램 (1) | 2023.12.09 |
|---|---|
| [알고리즘] 검색 1 -순차 검색, 이진 검색, 트리 검색 (0) | 2023.12.09 |
| [알고리즘] 정렬 5 - 기수 정렬 Radix Sort (0) | 2023.12.09 |
| [알고리즘] 정렬 4 - 병합 정렬(2-way, n-way) (0) | 2023.12.09 |
| [알고리즘] 정렬 3 - 삽입정렬, 셸 정렬 (0) | 2023.12.09 |