'C,C++ /Algorithm 문제풀이연습'에 해당되는 글 1건

  1. 2014.09.16 heap sorting sorce
2014. 9. 16. 15:34


힙소팅 정리한 소스 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;

}




Posted by k1rha