|
․Heap의 정의
․Heap의 종류
․우선순위 큐(Priority Queue)
․Heap
․힙 정렬의 방법
|
|
|
소트 비교
최악
평균
최선
추가 메모리
버블 정렬
O(n^2)
O(n^2)
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 log n)
O(n log n)
필요 없음
합병 정렬
O(n log n)
O(n log n)
O(n log n)
원소 수 만큼
힙
|
|
|
강점을 조합하는 것이다. 예를 들어 배열은 RAM 영역에 쉽게 포함될 수 있는 크기 단위로 나뉘어 질 수 있을 것이고 나뉘어진분할 리스트들을각기 퀵 소트나 힙 소트로 정렬한다. 그리고정렬된 분할 리스트들을 머지 소트로 병합하는 것이다.
|
|
|
list[], int n,int key_pos);
: 힙정렬 함수
5) void merge(SCORE list[], SCORE sorted[], int i, int m, int n,int key_pos);
: 병합정렬 보조함수
6) void merge_sort(SCORE list[], int n,int key_pos);
: 병합정렬 함수
7) void merge_pass(SCORE list[], SCORE sorted[], int n, int length,int key_pos);
:병합정
|
|
|
#include<stdio.h>
#include<time.h>
#define N 100000
void make_heap(int a[], int n);
void heapify(int a[], int n, int k);
void heap_sort(int a[], int n);
void swap(int *a, int *b);
void bubble_sort(int a[],int n);
clock_t before;
void start_time(void){
before=clock();
}
doubl
|
|
메뉴펼치기
