언제나 휴일

[C언어 알고리즘] 3.5.4 힙 정렬 알고리즘 소스 코드//힙 정렬 #include #define SWAP(a,b) {int t; t = a; a=b; b=t;}//a와 b를 교환 #define LCHILD(me) (2*me +1) #define RCHILD(me) (LCHILD(me)+1) #define PARENT(me) ((me-1)/2) void ViewArr(int *arr, int n); void HeapSort(int *base, size_t n); int main(void) { int arr[10] = { 9,4,3,10,5,8,7,6,2,1 }; ViewArr(arr, 10); HeapSort(arr, 10); ViewArr(arr, 10); return 0; } void HeapSor..

[C언어 알고리즘] 3.5.3 힙 정렬 알고리즘 구현 이번에는 힙 정렬 알고리즘을 구현해 보기로 해요. 힙 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리) 초기 힙 구성 루트와 맨 마지막 자손 교환 n을 1 감소 반복(n: n->1) 힙 구성 루트와 맨 마지막 자손 교환 n을 1 감소 초기 힙 구성(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리) 반복(i:1->n) j:=1 반복(j>0) pa:=PARENT(j) 조건: compare(base[j], base[pa])이 0보다 크면 base[j], base[pa] 교환 j: = pa 아니면 내부 루프 탈출 힙 구성(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리) 반복 lc:=..

[C언어 알고리즘] 3.5.2 힙 정렬 알고리즘 성능 분석 이번에는 힙 정렬 알고리즘의 수행 속도를 계산해 보기로 해요. 힙 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리) 초기 힙 구성 루트와 맨 마지막 자손 교환 n을 1 감소 반복(n: n->1) 힙 구성 루트와 맨 마지막 자손 교환 n을 1 감소 힙 정렬 알고리즘 수행 속도는 초기 힙 구성과 힙 구성을 n-1번 수행하는 비용의 합입니다. 수행 속도 = 초기 힙 구성 속도 + 힙 구성 속도 * (n-1) 초기 힙 구성(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리) 반복(i:1->n) j:=1 반복(j>0) pa:=PARENT(j) 조건: compare(base[j], base[pa])이 0보다..

[C언어 알고리즘] 3.5.1 힙 정렬 알고리즘 소개 힙 정렬은 힙 트리를 이용하는 알고리즘입니다. 최대 힙을 사용하면 크기 순(Ascend)으로 정렬하고 최소 힙을 사용하면 크기 역순(Descend)으로 정렬합니다. 힙 정렬은 먼저 힙 트리를 구성합니다. 그리고 루트의 값과 맨 마지막 값을 교환한 후에 정렬 범위를 1 줄입니다. 이와 같은 작업을 반복하여 정렬 범위가 1일 때까지 반복합니다. 최대 힙 트리에서 루트는 최대 값을 갖습니다. 따라서 마지막 값과 교환하면 제일 큰 값이 맨 뒤로 배치할 수 있습니다. 그리고 난 후에 정렬 범위를 줄여나가면 최종적으로 정렬 상태를 만들 수 있는 것입니다. 힙 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리) 초기 힙 구성 루트와 맨 ..

[C언어 알고리즘] 3.5 힙 정렬(Heap Sort) 알고리즘 이제 힙 정렬 알고리즘을 살펴보기로 해요. 힙 정렬은 완전 이진 트리의 한 종류인 힙 트리를 이용하여 정렬하는 알고리즘입니다. 먼저 힙 트리가 무엇인지 살펴본 후에 힙 정렬 알고리즘을 알아보고 분석 및 구현해 봅시다. 힙 트리는 부모의 값이 자식의 값보다 큰 값을 보장하는 최대 힙과 작은 값을 보장하는 최소 힙이 있습니다. 최대 힙으로 표현한 힙 트리의 루트에는 가장 큰 값을 갖고 최소 힙으로 표현하면 가장 작은 값을 갖습니다. [그림 3.12] 힙 트리 힙 트리처럼 완전 이진 트리는 배열로 많이 표현합니다. 완전 이진 트리가 아닌 이진 트리도 배열로 표현할 수 있지만 트리의 높이가 높아지고 한 쪽으로 기울어질 수록 비어있는 공간이 많아져서..

[C언어 알고리즘] 3.3.3 퀵 정렬 알고리즘 소스 코드//퀵 정렬(Quick Sort) #include #define SWAP(a,b) {int t; t = a; a=b; b=t;}//a와 b를 교환 int *origin; int on; void QuickSort(int *base, int n); void ViewArr(int *arr, int n); int main(void) { int arr[10] = { 9,4,3,10,5,8,7,6,2,1 }; origin = arr; on = 10; ViewArr(arr, 10); QuickSort(arr, 10); ViewArr(arr, 10); return 0; } void PrintSpace(int n); void QuickSort(int *base, ..

[C언어 알고리즘] 3.3.2 퀵 정렬 알고리즘 구현퀵 정렬 알고리즘을 구현합시다. 퀵 정렬(base:컬렉션,n: 원소 개수, compare:비교 논리) 조건(n

[C언어 알고리즘] 3.3.1 퀵 정렬 알고리즘 성능 분석 퀵 정렬 알고리즘 성능을 분석합시다. 퀵 정렬(base:컬렉션,n: 원소 개수, compare:비교 논리) 조건(n

[C언어 알고리즘] 3.3 퀵 정렬(Quick Sort) 알고리즘 퀵 정렬 알고리즘은 재귀적인 방법으로 문제를 해결하는 알고리즘입니다. 퀵 정렬 알고리즘은 피벗 값을 선택하여 피벗 값보다 작은 값들은 왼쪽으로 보내고 큰 값들은 오른쪽으로 보낸 후에 이들 사이에 피벗을 위치시키는 원리를 이용합니다. 이후 피벗보다 작은 값들을 재귀 호출로 정렬하고 피벗보다 큰 값들도 재귀 호출로 정렬하는 방식입니다. 그런데 퀵 정렬은 어떠한 요소를 피벗으로 선택하냐에 따라 성능에 차이가 납니다. 만약 전체 요소의 중간 순위의 요소를 선택하면 재귀 호출에서 반씩 나누어 정렬을 하게 되어 좋은 성능을 발휘합니다. 하지만 가장 작은 값이나 가장 큰 값을 피벗으로 선택하면 최악의 성능을 발휘합니다. 여기에서는 맨 앞과 맨 뒤, 그..

[C언어 알고리즘] 3.2.3 하노이 타워 알고리즘 소스 코드//Program.c #include #include void Hanoi(const char *src, const char *use, const char *dest, int n) { if(n