힙소팅 정리한 소스 heap sorting sorce
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 10 // 배열 사이즈 정의
void create_random_data( int heap_array[], int size );
void display( int array[],int size );
void reverse_display( int array[], int size );
void create_heap_tree( int heap_array[] , int size );
void swap( int heap_array[], int index );
void heap_sorting( int heap_array[], int sort_array[] , int size );
int swap_sort( int heap_array[] , int size );
int min( int a , int b );
void main() {
clock_t start,finish;
int heap_array[SIZE];
int sort_array[SIZE];
/*random create */
printf("<< Random Data >>\n");
create_random_data(heap_array,SIZE); //랜덤 데이타 생성
display(heap_array,SIZE);
create_heap_tree(heap_array,SIZE); //힙 트리 생성
printf("\n<< Create_heap_tree Data >>\n");
display(heap_array,SIZE);
heap_sorting(heap_array,sort_array,SIZE); //힙 소팅 함수 호출
printf("\n<< Sorted Data >>\n");
display(sort_array,SIZE);
printf("\n<< Reverse Sorted Data >>\n");
reverse_display(sort_array,SIZE);
printf("\n");
}
void create_random_data(int heap_array[], int size) {
int i;
for(i=0 ; i<size ; i++)
heap_array[i] = rand()%size*3;
}
////////////////////////////////////////////////////////////////
//함수명 : display
//용도 : 배열을 출력한다.
//매개변수 : 배열 포인터,배열 사이즈
//리턴값 : 출력시간(정수)
void display(int array[], int size) {
int i;
for(i=0 ; i<size ; i++)
printf("%d ",array[i]);
printf("\n");
}
void reverse_display(int array[], int size) {
int i;
for(i=size-1 ; i>=0 ; i--)
printf("%d ",array[i]);
}
void create_heap_tree(int heap_array[], int size) {
int i;
for(i=1 ; i<size ; i++)
swap(heap_array,i);
}
/*create Heap 에 사용 되며, 상위 노드가 하위 노드보다는 반드시 작도록 배치한다.*/
void swap(int heap_array[], int index) {
int temp;
int swap_flag = 1;
while(swap_flag && index != 0) { //루트 이거나 swap이 일어나지 않으면 종료
swap_flag = 0; //swap을 감시하는 플래그
//index%2 == 1 이면 좌측 자식이다 (현재가 자식이다.. 루트이면 그냥 넘어감)
if(index%2 == 1 && heap_array[index] < heap_array[(index-1)/2]) {
heap_array[index] = heap_array[index] ^ heap_array[(index-1)/2];
heap_array[(index-1)/2] = heap_array[index] ^ heap_array[(index-1)/2];
heap_array[index] = heap_array[index] ^ heap_array[(index-1)/2];
index = (index-1)/2;
swap_flag = 1;
}
//index%2 == 0 이면 우측 자식이다(현재가 자식이다.. 루트이면 그냥 넘어감)
if(index%2 == 0 && heap_array[index] < heap_array[(index-2)/2]) {
heap_array[index] = heap_array[index] ^ heap_array[(index-2)/2];
heap_array[(index-2)/2] = heap_array[index] ^ heap_array[(index-2)/2];
heap_array[index] = heap_array[index] ^ heap_array[(index-2)/2];
index = (index-2)/2;
swap_flag = 1;
}
}
}
/* 힙트리의 배열에서 루트값을 빼내면서 소팅한다 */
void heap_sorting( int heap_array[], int sort_array[], int size ) {
int i = 0;
int heap_array_size;
heap_array_size = size;
for( i=0 ; i<size ; i++ ) {
sort_array[i] = swap_sort( heap_array, heap_array_size );
heap_array_size--;
}
}
/* 최상위 root가 제일 작도록 소팅함. root 값에 최 하위 값 (상대적으로 큰값)
을 넣고 자식 노드와 비교해가며 정렬함 */
int swap_sort(int heap_array[], int size) {
int sort_value;
int swap_flag = 0;
int i = 0;
/* swap이 발생하지 않거나 인덱스가 size를 초과 하면 종료한다 */
while( swap_flag == 0 && !( ((i*2)+1 >= size-1) && ( (i*2)+2 >=size-1) ) ) {
swap_flag = 1;
///////////////////////////////////////////////////////////////////
// 좌 우 자식중 더 작은값(min함수 호출)과 비교한다
// 작은 값이 없다면.. 리턴! why? 힙소팅 create 부분에서 이미 상위
// 노트가 하위 노드보다는 반드시 작도록 설정 되었기 때문!
// 좌 우 중 작은쪽이 있다면 작은 쪽의주로 정렬을 해 드러간다.
if( heap_array[i] > min( heap_array[(i*2)+1] , heap_array[(i*2)+2] ))
{
if(heap_array[(i*2)+1] < heap_array[(i*2)+2]) {
heap_array[i] = heap_array[i] ^ heap_array[(i*2)+1];
heap_array[(i*2)+1] = heap_array[i] ^ heap_array[(i*2)+1];
heap_array[i] = heap_array[i] ^ heap_array[(i*2)+1];
i = (i*2)+1;
}
else {
heap_array[i] = heap_array[i] ^ heap_array[(i*2)+2];
heap_array[(i*2)+2] = heap_array[i] ^ heap_array[(i*2)+2];
heap_array[i] = heap_array[i] ^ heap_array[(i*2)+2];
i = (i*2)+2;
}
swap_flag = 0;
}// end if
}// end while
/* 젤 작은 root 값을 넘겨주고, root는 현트리의 제일 마지막 노드로 교체됨 */
sort_value = heap_array[0];
heap_array[0] = heap_array[size-1];
return sort_value;
}
int min(int a, int b) {
if(a < b) return a;
else return b;
}
