기수정렬과 히프정렬

목차

1. 기수정렬
1). 기수정렬의 의의
2). 기수 교환 정렬의 전략
3). 기수 교환 정렬 함수
4). 직접 기수 정렬의 전략

2. 히프정렬
1). 특징
2). 복잡도 분석
3). 장점
4). 단점
5). 알고리즘

본문내용

노드 아래로 정렬이 된다.
2). 복잡도 분석- 최대 히프 구조 초기 생성 : O(n logn)- 최대 히프 재구성 : 매회 최대 O(logn), 총 n-1 회- 전체 비교 회수 : O(n logn)3). 장점- 수행 시간이 아주 우수하다. O(nlogn)4). 단점- 추가 기억공간이 불필요하다. 5). 알고리즘(C로 설명한 알고리즘과 강의록 참고)void Max_heap(data A[], int root, int n){ int child; data root_data; root_data = A[root]; child = root * 2; //자식노드가 있는 동안 계속적으로 반복 while(child <= n) // 자식노드가 n 보다 커지면 루프를 빠져나온다. { if(child A[child]) break; else{ A[child/2] = A[child]; child = child * 2; } } A[child/2] = root_data;}#define swap(x,y,t)((t)=(x), (x)=(y), (y)=(t))void Heap_Sorting(data A[], int n){ int i, j; data temp; // 최대 히프 구조 생성 for(i = n/2l i>0; i--) { swap(A[1], A[i+1], temp); Max_heap(A,1,i); }}

키워드

기수정렬,   히프정렬,   알고리즘