[DATASTRUCTURE] Heap Sort

ALGORITHM/ALGORITHM STUDY

[DATASTRUCTURE] Heap Sort

l_j_yeon 2017. 3. 30. 19:11

Heap Sort 개념 : http://priv.tistory.com/61

sort.h

function.h

#pragma once
#include "sort.h"

int Square(int Data)
{
	int result = 1;
	for (int i = 0; i < Data; i++) result *= 2;
	return result;
}

void Show_Heap_Sort_Tree()
{
	int Square_Count = 0, Tree_Count = 0;

for (int i = 0; i < HEAP_TREE_COUNT; i++)
	{
		cout << Heap_Sort_Tree[i] << " ";
		Tree_Count++;
		if (Tree_Count == Square(Square_Count))
		{
			Square_Count++;
			Tree_Count = 0;
			cout << "\n";
		}
	}
}

/****Instruct Function****/
// File open and Make Tree
void Instuct()
{
	ifstream fcin_input;
	fcin_input. open("input.txt");
	int Data;
	while (!fcin_input.eof())
	{
		fcin_input >> Data;
		Insert(Data);
	}
}

/****Command Function****/
// Get Commandation from User
void Command()
{
	int Command = 0;
	Initialize();
	Instuct();

while (1)
	{
		cout << "1. 삽입 2. Show_Min_Heap_Sort 3. Show_Tree \n";
		cin >> Command;
		switch (Command)
		{
		case 1:
			int Data;
			cout << "Data를 입력해주세요. \n";
			cin >> Data;
			Insert(Data);
			Show_Heap_Sort_Tree();
			system("pause"); system("cls");
			break;
		case 2:
			Heap_Flag = HEAP_FLAG_OFF;
			Delete();
			system("pause"); system("cls");
			break;
		case 3:
			Show_Heap_Sort_Tree();
			system("pause"); system("cls");
			break;
		}
	}
}

/****Switch Function****/
void Switch(int Index_1, int Index_2)
{
	int Data = Heap_Sort_Tree[Index_2];
	Heap_Sort_Tree[Index_2] = Heap_Sort_Tree[Index_1];
	Heap_Sort_Tree[Index_1] = Data;
}

/****Initialize Function****/
// Initialize Array (Heap_Tree)
void Initialize()
{
	for (int i = 0; i < HEAP_TREE_COUNT; i++)
	{
		Heap_Sort_Tree[i] = NO_DATA;
	}
}

/****Insert Function****/
// Insert Array (Heap_Tree)
// Get Data
void Insert(int Data)
{
	if (Heap_Flag == HEAP_FLAG_OFF)
	{
		Heap_Sort_Tree[ROOT_INDEX] = Data;
		Heap_Flag = HEAP_FLAG_ON;
		Insert_Index++;
	}
	else
	{
		Insert_Index++;
		Heap_Sort_Tree[Insert_Index] = Data;
		Up_Heap(PARENT(Insert_Index), Insert_Index);
	}
}

void Up_Heap(int Parent_Index, int Present_Index)
{
	if (Heap_Sort_Tree[Parent_Index] > Heap_Sort_Tree[Present_Index])
	{
		Switch(Parent_Index, Present_Index);
		
		if (PARENT(Present_Index) != ROOT_INDEX)
		{
			Present_Index = PARENT(Present_Index);
			Up_Heap(PARENT(Present_Index), Present_Index);
		}
	}
}

void Delete()
{
	if (Heap_Sort_Tree[ROOT_INDEX] > NO_DATA)
	{
		cout << Heap_Sort_Tree[ROOT_INDEX] << " ";
		Heap_Sort_Tree[ROOT_INDEX] = Heap_Sort_Tree[Insert_Index];
		Heap_Sort_Tree[Insert_Index] = NO_DATA;
		Insert_Index--;
		Down_Heap(ROOT_INDEX);
		Delete();
	}
}

int Down_Heap(int Present_Index)
{
	if (Heap_Sort_Tree[Present_Index]>NO_DATA)
	{
		int Left_Child_Flag = LEFT_CHILD_FLAG_OFF;
		int Right_Child_Flag = RIGHT_CHILD_FLAG_OFF;

if (Heap_Sort_Tree[LEFT_CHILD(Present_Index)] > NO_DATA)
		{
			if (Heap_Sort_Tree[LEFT_CHILD(Present_Index)] < Heap_Sort_Tree[Present_Index]) Left_Child_Flag = LEFT_CHILD_FLAG_ON;
		}
		
		if (Heap_Sort_Tree[RIGHT_CHILD(Present_Index)] > NO_DATA)
		{
			if (Heap_Sort_Tree[RIGHT_CHILD(Present_Index)] < Heap_Sort_Tree[Present_Index]) Right_Child_Flag = RIGHT_CHILD_FLAG_ON;
		}

if (Left_Child_Flag == LEFT_CHILD_FLAG_ON && Right_Child_Flag == RIGHT_CHILD_FLAG_ON)
		{
			if (Heap_Sort_Tree[RIGHT_CHILD(Present_Index)] < Heap_Sort_Tree[LEFT_CHILD(Present_Index)])
			{
				Switch(RIGHT_CHILD(Present_Index), Present_Index);
				return Down_Heap(RIGHT_CHILD(Present_Index));
			}
			else
			{
				Switch(LEFT_CHILD(Present_Index), Present_Index);
				return Down_Heap(LEFT_CHILD(Present_Index));
			}
		}

if (Left_Child_Flag == LEFT_CHILD_FLAG_ON)
		{
			Switch(LEFT_CHILD(Present_Index), Present_Index);
			return Down_Heap(LEFT_CHILD(Present_Index));
		}

if (Right_Child_Flag == RIGHT_CHILD_FLAG_ON)
		{
			Switch(RIGHT_CHILD(Present_Index), Present_Index);
			return Down_Heap(RIGHT_CHILD(Present_Index));
		}
	}
}

Heap_Sort.cpp

저작자표시 비영리 변경금지 (새창열림)