Heap sort

lsh950223·2020년 5월 18일
0

안녕하세요 c++ 공부하고있는 대학생입니다.
이번에는 저번에 max_heap 구성 한 것에 대한 heap sort에 대해 정리 해 보려고 합니다.

이전에 구성했던 코드에서 max_heap으로 구성한 그림입니다.
이진트리 특성상, 부모노드를 기준으로 왼쪽 자식노드부터 채워지기때문에, 인덱스를 보시면
root 노드인 9가 0번인덱스,
4가 1번인덱스,
7이 2번인덱스,
2가 3번인덱스,
3이 4번인덱스,
2가 5번인덱스,
2가 6번인덱스
이 순서대로 채워집니다.

heap sort의 원리는 다음과 같습니다.

  1. 비교해서 볼 노드는, 전체 노드의 개수에서 /2 (몫 연사자)를 한 값이다. (ex. 7개면, 3개만 보면된다.)
  1. 제일 마지막 노드와 root 노드를 비교해서 값이 마지막 노드가 크다면 swap한다.
  2. 마지막 노드의 부모노드와 비교해서 , 부모 노드가 크다면 swap한다.

처음에는 이렇게 9와 2를 바꾸어줍니다.

이러한 과정을 다 거치면..

이렇게 모두 바뀌게 됩니다.

우선 먼저 max_heap에 대한 소스코드입니다.

void heapify(node* root, int size) {
	int i = size - 1;
	do {
		if (root[0].data < root[i].data) {
			int temp = root[0].data;
			root[0].data = root[i].data;
			root[i].data = temp;
		}
		if (root[i].data > root[(i - 1) / 2].data) {	
			int temp = root[i].data;
			root[i].data = root[(i - 1) / 2].data;
			root[(i - 1) / 2].data = temp;
		}
		if (i <= (size - 1) / 2) {

			if (root[i].data < root[(i + 1) * 2].data && root[(i + 1) * 2].right != NULL) {

				int temp = root[i].data;
				root[i].data = root[(i + 1) * 2].data;
				root[(i + 1) * 2].data = temp;
			}

			if (root[i].data < root[(i * 2) + 1].data && root[(i * 2) + 1].left != NULL) {
				int temp = root[i].data;
				root[i].data = root[(i * 2) + 1].data;
				root[(i * 2) + 1].data = temp;
			}
		}
		i--;
	} while (i != 0);
}

그리고 heapsort에 대한 소스코드입니다.

void heapsort(node* root, int size) {
	int i = size - 1;
	int sizeNum = size - 1;
	do {
		int temp = root[0].data;
		root[0].data = root[i].data;
		root[i].data = temp;

		root[i].left = NULL;
		root[i].right = NULL;

		if(i>1) heapify(root, i);
		i--;
	} while (i >= 0);
	
}

do while 루프문을 통해서 비교할 노드 전체를 대상으로 접근하는 방식입니다.
완전히 swap된 노드는 더이상 비교 할 필요가 없기때문에, data값을 제외한 왼쪽 오른쪽 노드를 NULL값으로 끊어주기 위해 사용하였습니다.
if문을 통해 root노드가 아니라면, 비교 해 줄 필요가없기때문에 heapify 함수 호출을 통해 heapify 안에서 재귀문으로 조건에 맞춘 모습입니다.

이렇게해서 결과를 보여드리면,

inputdata는 제가 넣은 데이터이고, origin은 이진트리에 들어간 데이터입니다. 이진트리에서 제가 전위순회를 했기때문에, 9 2 4 7 3 2 2 순으로 출력되는것입니다.
heapify는 max_heap입니다. 출력을보면 max_heap이 형성된걸 볼 수 있습니다.
마지막으로 heapsort를 통해 2 2 2 3 4 7 9 로 출력됨을 볼 수 있습니다.

전체 소스코드를 올리며 정리를 마무리 하도록 하겠습니다.

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

#define MAX_SIZE 256

typedef struct node {
	struct node* left;
	struct node* right;
	int data;
}node;

typedef struct tree {
	struct tree* next;
	int data;
}tree;

tree* root = NULL;
int size = 1;

tree* insert(tree* root, int data) {
	if (root == NULL) {
		root = (tree*)malloc(sizeof(tree));
		root->next = NULL;
		root->data = data;
		size++;
		return root;
	}
	else {
		root->next = insert(root->next, data);
		return root;
	}
}

void print(node* root) {
	if (root) {
		printf("%d ", root->data);
		print(root->left);
		print(root->right);
	}
}

void swap(int *a, int *b) {
	int *temp = a;
	a = b;
	b = temp;
}

void heapify(node* root, int size) {
	int i = size - 1;
	do {
		if (root[0].data < root[i].data) {
			int temp = root[0].data;
			root[0].data = root[i].data;
			root[i].data = temp;
		}
		if (root[i].data > root[(i - 1) / 2].data) {	
			int temp = root[i].data;
			root[i].data = root[(i - 1) / 2].data;
			root[(i - 1) / 2].data = temp;
		}
		if (i <= (size - 1) / 2) {

			if (root[i].data < root[(i + 1) * 2].data && root[(i + 1) * 2].right != NULL) {

				int temp = root[i].data;
				root[i].data = root[(i + 1) * 2].data;
				root[(i + 1) * 2].data = temp;
			}

			if (root[i].data < root[(i * 2) + 1].data && root[(i * 2) + 1].left != NULL) {
				int temp = root[i].data;
				root[i].data = root[(i * 2) + 1].data;
				root[(i * 2) + 1].data = temp;
			}
		}
		i--;
	} while (i != 0);
}

void heapsort(node* root, int size) {
	int i = size - 1;
	int sizeNum = size - 1;
	do {
		int temp = root[0].data;
		root[0].data = root[i].data;
		root[i].data = temp;

		root[i].left = NULL;
		root[i].right = NULL;

		if(i>1) heapify(root, i);
		i--;
	} while (i >= 0);
	
}

int main() {
	node binary[MAX_SIZE];

	int size = 7;
	printf("input data\n");
	for (int i = 1; i <= size; i++) {
		int key = 0;
		scanf_s("%d", &key);
		root = insert(root, key);
		binary[i].data = root->data;
		binary[i].left = NULL;
		binary[i].right = NULL;

		root = root->next;

		if (i % 2 == 0) {
			binary[i / 2].left = &binary[i];
		}
		else {
			binary[i / 2].right = &binary[i];
		}
	}
	printf("origin\n");
	print(&binary[1]);
	printf("\n");
	printf("heapify result\n");
	heapify(&binary[1], size);
	print(&binary[1]);
	printf("\n");
	printf("heap result \n");
	heapsort(&binary[1], size);
	printf("\n");
	for (int i = 1; i <= size; i++) {
		printf("%d ", binary[i].data);
	}
}

heap sort를 구현하면서.. 되도록이면 직접 그림을 그려서 풀었습니다. 제가 자료구조를 공부할 때 주의깊게 보는점은..

  1. 의사코드를 작성하면서 어떻게 자료구조를 적용 할 지 고민한다.
  1. 그림을 그리면서 작성한 의사코드를 베이스로 잡는다.
  2. 소스코드로 구현하면서 구상대로 되었는지 확인한다.

이렇게 보면서 공부합니다.
그리고 실질적인 프로젝트를하면서 제가 c와 c++을 사용하면서 메모리에대한 벽에 자주 막히는 경우가 있습니다. 그때마다 잘 생각해보면, 자료구조로 어려움을 잘 빠져나왔었습니다.
자료구조가 항상 답은 아니지만, 공간복잡도 시간복잡도에 있어서 이득을 많이 주는 파트이기때문에, 더 열심히 공부하고 프로젝트의 상황에따라 어떤 자료구조를 사용 할 지, 생각 해 보는것도 중요하다고 생각합니다.
아직 미숙한 실력이지만 더욱 더 최적화되고 좋은 코드를 작성 할 수 있도록 노력하는것이 지금의 제가 하고있는 공부에서 가장 중요하게 생각하고있습니다. 그를 위해서는.. 컴구론, os도 공부를 열심히 해야한다고 생각합니다.

profile
C++ 공부하고있는 대학생입니다.

0개의 댓글