Winner Tree

[승자트리를 이용한 정렬]

10개의 정수형 원소로 구성된 k 개의 run에 대하여 승자트리 (winner tree)를 이용하여 정렬을 수행하라. 이때 k는 2의 누승 ( power of 2 )임을 가정하 라. 단 승자는 키 값이 작은 노드이다.

 

난수생성을 위한 seed와 k를 입력받는다.

 

k x 10의 2차원 배열을 생성한 뒤 정렬을 수행한다.

 

1~500 사이에서 발생시킨 k 개의 난수를 key로 사용하여 각 레코드에 k부터 k+9까지의 숫자를 순서대로 배열에 저장한다.(각 key는 중복 가능하다.)

 

Example

생성한 키 데이터에 대해 초기 승자트리를 구성한다.

 

승자트리를 사용한 정렬을 수행한다.

 

최소키를 sorted 배열에 저장 -> 최소키가 최종 승자로 선택된 레코드에는 다음 키 값으 로 nums 배열의 값을 치환(레코드의 키 값을 다 소진한 경우에는 무한대를 의미하는 임의 의 값으로 최소키를 치환) -> 승자트리를 재구성

 

이 과정을 k * 10번 반복함(승자트리를 재구성 시, 치환된 키의 index -> parent index -> sibling index를 구할 수 있음. 치환된 키와 sibling 키의 비교를 루트 방향으로 수행함)

 

정렬된 결과를 출력 출력한다.

 

Result

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

enum {
	MEMORY_OPEN_ERROR
};

#define NAME(a) #a
#define CATCH(ERROR) do{printf(NAME(ERROR));exit(0);}while(false)
#define CALLOC(type,data_num,ptr) do{if(!(ptr=(type*)calloc(data_num,sizeof(type)))){CATCH(MEMORY_OPEN_ERROR);}}while(false)
#define CALLOC_2D(type,row,col,ptr)do{CALLOC(type*,row,ptr);int iter;for(iter = 0; iter < row; iter++)CALLOC(type,col,ptr[iter]);}while(false)

#define RUN_SIZE 10
int* winner_tree;
int* index_ary_of_each_run;
int** run_table;

#define INF 123456789
#define RAND_RANGE 500
#define RAND_NUM (rand()%RAND_RANGE+1)

void make_run_table(void);

#define SWAP(type,x,y) do{type t=x;x=y;y=t;}while(false)
void sorting_run_table(void);

#define PRINT_NUM(num) (num==INF) ? (printf(" INF")) : (printf("%4d",num))
void print_run_table(void);

void init_winner_tree(void);

int* result;
int iter_result = 0;
void sort_with_winner_tree(void);

void print_result(void);

int run_number;
int seed_value;
int main(void)
{
	printf("< Sorting with winner tree >\n");

	printf("Enter the number of runs (4, 8, 16, 32 as a power of 2) >> ");
	scanf_s("%d", &run_number);

	CALLOC_2D(int, RUN_SIZE + 1, run_number, run_table);
	CALLOC(int, run_number, index_ary_of_each_run);
	CALLOC(int, run_number * 2, winner_tree);

	CALLOC(int, (run_number * RUN_SIZE), result);

	printf("Enter the seed value >> ");
	scanf_s("%d", &seed_value);

	srand(seed_value);

	printf("\n< Initialize Run Table >\n");
	make_run_table();
	sorting_run_table();
	print_run_table();

	printf("\n< Sorting >\n");
	init_winner_tree();

	sort_with_winner_tree();

	print_result();
	return 0;
}

void make_run_table(void)
{
	int i, j;
	for (j = 0;j < run_number;j++)
	{
		for (i = 0;i < RUN_SIZE;i++)
			run_table[i][j] = RAND_NUM;
		run_table[i][j] = INF;
	}
}

void sorting_run_table(void)
{
	int i, j, k;
	for (j = 0;j < run_number;j++)
	{
		for (k = 0;k < RUN_SIZE;k++)
			for (i = 0;i < RUN_SIZE - 1;i++)
				if (run_table[i][j] > run_table[i + 1][j])
					SWAP(int, run_table[i][j], run_table[i + 1][j]);
	}
}

void print_run_table(void)
{
	printf("initial_records\n");
	int i, j;
	for (j = 0;j < run_number;j++)
	{
		printf("%d-th run\n", j + 1);
		for (i = 0;i < RUN_SIZE;i++)
			PRINT_NUM(run_table[i][j]);
		printf("\n");
	}
	printf("\n");
}

void init_winner_tree(void)
{
	int i;
	for (i = run_number;i < (2 * run_number);i++)
	{
		winner_tree[i] = i - run_number;
		index_ary_of_each_run[i - run_number] = 0;
	}

	int l_ch_winner_tree_value, r_ch_winner_tree_value;
	int l_ch_run_table_value, r_ch_run_table_value;

	for (i = run_number / 2;i >= 1;)
	{
		l_ch_winner_tree_value = winner_tree[i * 2];
		r_ch_winner_tree_value = winner_tree[i * 2 + 1];

		l_ch_run_table_value = run_table[index_ary_of_each_run[l_ch_winner_tree_value]][l_ch_winner_tree_value];
		r_ch_run_table_value = run_table[index_ary_of_each_run[r_ch_winner_tree_value]][r_ch_winner_tree_value];

		winner_tree[i] = (l_ch_run_table_value > r_ch_run_table_value) ? (r_ch_winner_tree_value) : (l_ch_winner_tree_value);

		if (((++i) % 4) == 0) i /= 4;
		else if (i == 2)break;
	}
}

void sort_with_winner_tree(void)
{
	int l_ch_winner_tree_value, r_ch_winner_tree_value;
	int l_ch_run_table_value, r_ch_run_table_value;

	int i;
	for (iter_result = 0;iter_result < (run_number * RUN_SIZE);iter_result++)
	{
		result[iter_result] = run_table[index_ary_of_each_run[winner_tree[1]]++][winner_tree[1]];

		for (i = run_number / 2;i >= 1;)
		{
			l_ch_winner_tree_value = winner_tree[i * 2];
			r_ch_winner_tree_value = winner_tree[i * 2 + 1];

			l_ch_run_table_value = run_table[index_ary_of_each_run[l_ch_winner_tree_value]][l_ch_winner_tree_value];
			r_ch_run_table_value = run_table[index_ary_of_each_run[r_ch_winner_tree_value]][r_ch_winner_tree_value];

			winner_tree[i] = (l_ch_run_table_value > r_ch_run_table_value) ? (r_ch_winner_tree_value) : (l_ch_winner_tree_value);

			if (((++i) % 4) == 0) i /= 4;
			else if (i == 2) break;
		}
	}
}

void print_result(void)
{
	int i;
	for (i = 0;i < iter_result;i++)
	{
		PRINT_NUM(result[i]);
		if ((i + 1) % RUN_SIZE == 0)printf("\n");
	}
	printf("\n");
}