정렬알고리즘_힙 정렬 [6/8]

[ 힙 정렬이란? ]

• 이진 트리에 기반한 힙 트리구조를 만들어가며 배열을 정렬시킴
• 병합정렬의 메모리 효율성 문제를 해결하면서 O(n*logN)의 시간 복잡도를 보장
• 결국 시간복잡도가 log지수의 증가를 가지려면 소그룹으로 분리시켜 정렬해나가야 함
• 소그룹으로 쪼개서 정렬하는 방법에 힙 트리(이진 트리) 구조가 적용된 방식이라 볼 수 있음

​[ 이진 트리란? ]

• 하나의 노드에 자식 노드가 2개 이하인 트리 구조

​[ 힙 트리란? ]

• 이진 트리 구조에서, 노드 간의 관계에 규칙성이 적용 된 구조
• 최대 힙 구조 : 부모 노드가 자식 노드보다 값이 큼 (가장 위 root 값이 최대값이 됨)
• 최소 힙 구조 : 최대 힙 구조와 반대
• 이진 트리를 최대 힙 또는 최소 힙 구조로 완성시킴 (최대값, 최소값을 빠르게 찾을 수 있음)

---

 

• 힙 트리를 한번 만들면 힙트리의 특성을 이용해 효율적으로 최대값 또는 최소값을 찾을 수 있음
• 힙트리를 한 번 만들고 이후 정렬 과정을 거침

 

• 힙트리가 완성된 이후 root값을 마지막 값과 바꾼 후 다시 최대값을 찾음
• 한 줄기의 자식노드만 확인해주면 힙트리가 계속 유지되기 때문에 매우 효율적인 구조

 

 

---

 

실제로 배열 안에서는 트리구조가 아닌 일반 규칙성을 가진 로직이기 때문에.. 규칙만 잘 찾아서 하나의 힙 트리만 완성시키고 나머지는 반복문으로 처리해주면 간단할 것 같습니다. 코딩이야 어떻게든 하면 되는건데 이런 구조나 로직을 만들어내는 분들이 참 존경스럽네요. 강의 코드를 보기 전 자체 코드를 한 번 짜보겠습니다. 이번 건 병합이나 퀵정렬에 비해 그리 어렵진 않아 보입니다.

 

실제 코드 구성도 병합, 퀵정렬에 비해 어렵진 않습니다. 재귀함수에 익숙해져서 그런지 뻑하면 재귀함수 호출을 쓰고 있네요. 처음엔 이런걸 어디다 쓰나 했는데.. 같은 로직을 연결된 곳에서 반복 수행할 때는 재귀함수가 참 편리한 것 같습니다.

#include <stdio.h>
void heap_arrange(int* arr, int size);
void node_swap(int* arr, int i);
void swap(int* arr, int x, int y);

void main()
{
	int arr[] = { 9, 8, 2, 10, 15, 12, 3, 22, 0, 3, 1, 1 };
	int size = sizeof(arr) / sizeof(int);

	/* 배열 출력 */
	printf("\n 정렬 전 : ");
	for (int i = 0; i < size; i++)
		printf("%d ", arr[i]);

	/* 정렬 */
	heap_arrange(arr, size);

	/* 배열 출력 */
	printf("\n 정렬 후 : ");
	for (int i = 0; i < size; i++)
		printf("%d ", arr[i]);

	printf("\n");
}

void heap_arrange(int* arr, int size)
{
	/* 최초 힙트리 생성 (자식노드 기준, 부모노드보다 작아야함) */
	for (int i = 1; i < size; i++)
		node_swap(arr, i);
	swap(arr, 0, size - 1);	// 처음과 마지막을 바꿔줌

	/* 정렬 수행 (자식노드가 있는 부모노드만 보면 됨) */
	for (int size_t = size - 1; size_t > 1; size_t--)
	{
		/* 자식노드가 있는 부모노드만 확인 */
		for (int i = 0, child = i * 2 + 1; i < size_t / 2; i++)
		{
			/* 자식 노드가 두 개 있으면 비교해서 큰 값을 지정 */
			if (child + 1 < size_t && arr[child] < arr[child + 1])
				child++;

			/* 자식노드 > 부모노드일 경우 바꿔주고 부모노드들도 확인 */
			if (arr[i] < arr[child])
			{
				swap(arr, i, child);
				node_swap(arr, i);
			}
		}
		swap(arr, 0, size_t - 1);	// 마지막 값과 바꿔줌
	}
}

/* 부모노드 모두 확인하기 */
/* parameter : 배열, 해당 노드 위치 */
/* return : void */
void node_swap(int* arr, int i)
{
	int parent_node = (i - 1) / 2;	// 부모 노드 주소

	/* root에 도달하거나 부모노드보다 작으면 리턴 */
	if (i == 0 || arr[i] < arr[parent_node])
		return;

	/* 부모노드 < 자식노드이면 바꿔주고 반복 수행 */
	if (arr[i] > arr[parent_node])
	{
		swap(arr, i, parent_node);
		node_swap(arr, parent_node);
	}
}

/* swap */
/* parameter : 배열, 바꿀 위치 두 개*/
/* return : void*/
void swap(int* arr, int x, int y)
{
	int temp = arr[x];
	arr[x] = arr[y];
	arr[y] = temp;
}

 

그럼 강의 코드를 확인하고 와볼게요.

유투브 '동빈나'님의 알고리즘 강의를 참고하였습니다.

 

---

 

강의에서는 do ~ while 이라는 처음보는 형식의 반복문을 사용하네요. 사실 부모노드를 찾는 일은 일정한 규칙으로 주소가 움직이기 때문에 재귀함수가 아닌 일반 반복문으로도 처리할 수 있습니다. 재귀함수는 함수 실행 시 나오는 결과를 다시 함수의 arguments로 줘서 실행시킬 때 (argument가 불규칙하게 나올 때) 가장 편리한 방식이므로 지금같은 경우는 굳이 재귀함수를 쓸 필요는 없긴 합니다. 전 연습삼아 써봤지만..

​

그리고 사실 이번 코드에서는 굳이 do ~ while을 쓸 필요 없이 일반 while문을 사용해도 됩니다. 무조건 먼저 한 번 수행해야하는 부분이 없어서요. 그냥 한 번 보여주실려고 써보신 것 같습니다. 혹시 몰라 일반 반복문으로 바꿔서 수행해봐도 같은 결과가 나오는 걸 확인했습니다.

​

추가로 최초 힙 구성을 할 때 자식노드가 부모노드보다 크지 않다면 그 부모노드의 부모노드를 검사하는 반복문은 break를 걸어주는게 좋습니다. 또한 정렬 시에도 자식노드가 없는 노드는 굳이 확인할 필요가 없으므로 그 부분에 대한 처리도 추가해주는게 좋습니다. 강의를 쉽게 하시기 위해 심플하게 작성하신 것 같아요.

 

※ Point (Do ~ while 구문)

- while의 조건을 충족할 때 Do 구문 안에 있는 내용을 수행

- Do { 수행내용 } while ( 조건 );

- 일반적인 while문과 비슷하나, 조건에 관계없이 무조건 {수행내용}을 한번 실행하고 반복문을 수행

- 그냥 while문은 조건을 충족하지 못하면 {수행내용}을 한번도 수행하지 않음

 

#include <stdio.h>
void swap(int* arr, int x, int y);
void heap_arrange(int* heap, int number);
void main()
{
	int heap[] = {9, 8, 2, 10, 15, 12, 3, 22, 0, 3, 1, 1};
	int number = sizeof(heap) / sizeof(int);
	
	/* 배열 출력 */
	printf("\n 정렬 전 : ");
	for (int i = 0; i < number; i++)
		printf("%d ", heap[i]);
	
	/* 정렬 */
	heap_arrange(heap, number);

		
	/* 배열 출력 */
	printf("\n 정렬 후 : ");
	for (int i = 0; i < number; i++)
		printf("%d ", heap[i]);
	
	printf("\n");
}

void heap_arrange(int* heap, int number)
{
	/* 최초 힙 구성 */
	for (int i = 1; i < number; i++)
	{
		int c = i;
		do
		{
			int root = (c - 1) / 2;
			if (heap[root] < heap[c])
				swap(heap, root, c);
			c = root;
		} while (c != 0);
    // heap[root] > heap[c] 일 경우 break 로직을 추가해주는 것이 좋음
	}

	/* 크기를 줄여가며 반복적으로 힙 구성 */
	for (int i = number - 1; i >= 0; i--)  
    // i > 1로 수정하고 위에 힙트리-정렬 사이에 swap을 한번 해주는게 좋을 듯
	{
		swap(heap, 0, i);  // 처음과 끝 교체
		int root = 0;
		int c = 1;
		do
		{
			c = 2 * root + 1;  // 자식노드
			if (c < i - 1 && heap[c] < heap[c + 1]) // 두번 째가 더 크면 c++
				c++;
			if (c < i && heap[root] < heap[c])
				swap(heap, root, c);
			root = c;

		} while (c < i);  // c < i/2 로 수정해주는 것이 좋음
	}
}


/* swap */
/* parameter : 배열, 바꿀 위치 두 개*/
/* return : void*/
void swap(int* arr, int x, int y)
{
	int temp = arr[x];
	arr[x] = arr[y];
	arr[y] = temp;
}