[자료구조 프로그래밍 연습문제] 힙 정렬 (heap sort)

heap sort

 

A. 배열 a[1]에서 a[11]에 11개의 999보다 큰 네자리 이상의 양의 정수가 저장되어 있다고 하자. 교재 Program 7.13: Heap sort의 함수 heapSort를 호출하여 이들을 오름순으로 정렬하는 과정을 확인하고자 한다. 이를 위해 Program 7.13에서 함수 adjust가 호출될 때마다 그 호출 직후 시점의 배열 a[1] 부터 a[11] 까지의 값을 출력하시오. 또한 정렬 진행 과정 설명을 위해 자신이 확인하고 싶은 기타 변수 값이 있으면 출력하시오. 출력된 값을 보고 배열을 complete binary tree로 그림을 그려서 해당 adjust의 수행 결과와 정렬 진행 과정에 대해 설명하시오. (complete binary tree 그림은 육필로 그려도 되고 자신이 작성한 프로그램에서 첫줄에 a[1], 그 다음 줄에 a[2]와 a[3], 그 다음 줄에 a[4]에서 a[7]까지, 그 다음 줄에 a[8]에서 a[11]까지를 출력해서 complete binary tree 모양을 대략 육안으로 확인할 수 있도록 해도 됨.)

 

정렬 데이터 요건 :
배열에 저장된 정렬할 수는 모두 999보다 큰 네자리 이상의 양의 정수로 한다. 값은 각자 임의로 정하고 배열에 저장하는 순서도 정렬되지 않은 순서로 각자 임의로 정한다. (예: a[1]=2356, a[2]=54362, ...., a[11]=1999).

 

 

1)  첫번째 실행

(1) 입력 배열 값

a[1].key = 9375; a[2].key = 5493; a[3].key = 3499; a[4].key = 2390;
a[5].key = 6748; a[6].key = 1436; a[7].key = 8072; a[8].key = 2353;
a[9].key = 8653; a[10].key = 5643; a[11].key = 8343;

 

(2) 정렬 진행 과정

1 : 입력 값
2 ~ 5 : 아래 위 노드를 비교하여 더 큰 값이 위에 오도록 swap (5번에서는 이미 정렬된
상태여서 변화 없음)
5 ~ 15 : 최고값(a[1])을 정렬되지 않은 배열의 마지막 노드에 이동, 위에서부터 큰 노드를
선택하여 빈자리를 채우고 최고값이 들어가는 자리의 노드 값은 자신의 위에 더 작은 값이
오지 않도록 적절한 자리를 찾아야 함 (이 실행에서는 항상 마지막 층)

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

typedef struct _element {
	int key;
} element;

void printelements(element a[])
{
	for (int i = 1; i < 12; i++) {
		printf("%d ", a[i].key);
	}
	printf("\n");
}

void adjust(element a[], int root, int n)
{
	int child, rootkey;
	element temp;
	temp = a[root];
	rootkey = a[root].key;
	child = 2 * root;
	while (child <= n) {

		if ((child < n) && (a[child].key < a[child + 1].key)) {
			child++;
		}

		if (rootkey > a[child].key) {
			break;
		}
		else {
			a[child/2] = a[child];
			child *= 2;
		}

		a[child / 2] = temp;
	}
	printelements(a);
}

void heapSort(element a[], int n)
{
	int i, j;
	element temp;

	for (i = n / 2; i > 0; i--) {
		adjust(a, i, n);
	}

	for (i = n - 1; i > 0; i--) {
		temp = a[1];
		a[1] = a[i + 1];
		a[i + 1] = temp;

		adjust(a, 1, i);
	}
}

int main() {
	element a[12];
	a[1].key = 9375; a[2].key = 5493; a[3].key = 3499; a[4].key = 2390; a[5].key = 6748; a[6].key = 1436 ;
	a[7].key = 8072; a[8].key = 2353; a[9].key = 8653; a[10].key = 5643; a[11].key = 8343;
	
	heapSort(a, 11);

	return 0;
}

 

 

2) 두번째 실행

(1) 입력 배열 값

a[1].key = 8376; a[2].key = 6746; a[3].key = 2499; a[4].key = 7823;
a[5].key = 3458; a[6].key = 9324; a[7].key = 1341; a[8].key = 5674;
a[9].key = 2349; a[10].key = 3457; a[11].key = 9023;

 

(2) 정렬 진행 과정

1 : 입력 값
2 ~ 5 : 아래 위 노드를 비교하여 더 큰 값이 위에 오도록 swap (2번에서는 이미 정렬된
상태여서 변화 없음)
5 ~ 15 : 최고값(a[1])을 정렬되지 않은 배열의 마지막 노드에 이동, 위에서부터 큰 노드를
선택하여 빈자리를 채우고 최고값이 들어가는 자리의 노드 값은 자신의 위에 더 작은 값이
오지 않도록 적절한 자리를 찾아야 함 (6번, 10번 참고)

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

typedef struct _element {
	int key;
} element;

void printelements(element a[])
{
	for (int i = 1; i < 12; i++) {
		printf("%d ", a[i].key);
	}
	printf("\n");
}

void adjust(element a[], int root, int n)
{
	int child, rootkey;
	element temp;
	temp = a[root];
	rootkey = a[root].key;
	child = 2 * root;
	while (child <= n) {

		if ((child < n) && (a[child].key < a[child + 1].key)) {
			child++;
		}

		if (rootkey > a[child].key) {
			break;
		}
		else {
			a[child/2] = a[child];
			child *= 2;
		}

		a[child / 2] = temp;
	}
	printelements(a);
}

void heapSort(element a[], int n)
{
	int i, j;
	element temp;

	for (i = n / 2; i > 0; i--) {
		adjust(a, i, n);
	}

	for (i = n - 1; i > 0; i--) {
		temp = a[1];
		a[1] = a[i + 1];
		a[i + 1] = temp;

		adjust(a, 1, i);
	}
}

int main() {
	element a[12];
	a[1].key = 8376; a[2].key = 6746; a[3].key = 2499; a[4].key = 7823; a[5].key = 3458; a[6].key = 9324;
	a[7].key = 1341; a[8].key = 5674; a[9].key = 2349; a[10].key = 3457; a[11].key = 9023;
	
	heapSort(a, 11);

	return 0;
}

 

 

3) 세번째 실행

 

(1) 입력 배열 값

a[1].key = 1343; a[2].key = 3466; a[3].key = 8567; a[4].key = 3684;
a[5].key = 8932; a[6].key = 6734; a[7].key = 6588; a[8].key = 3574;
a[9].key = 3689; a[10].key = 3687; a[11].key = 4563;

 

(2) 정렬 진행 과정

1 : 입력 값
2 ~ 5 : 아래 위 노드를 비교하여 더 큰 값이 위에 오도록 swap (3번에서는 이미 정렬된
상태여서 변화 없음)
5 ~ 15 : 최고값(a[1])을 정렬되지 않은 배열의 마지막 노드에 이동, 위에서부터 큰 노드를
선택하여 빈자리를 채우고 최고값이 들어가는 자리의 노드 값은 자신의 위에 더 작은 값이
오지 않도록 적절한 자리를 찾아야 함 (7번 참고)

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

typedef struct _element {
	int key;
} element;

void printelements(element a[])
{
	for (int i = 1; i < 12; i++) {
		printf("%d ", a[i].key);
	}
	printf("\n");
}

void adjust(element a[], int root, int n)
{
	int child, rootkey;
	element temp;
	temp = a[root];
	rootkey = a[root].key;
	child = 2 * root;
	while (child <= n) {

		if ((child < n) && (a[child].key < a[child + 1].key)) {
			child++;
		}

		if (rootkey > a[child].key) {
			break;
		}
		else {
			a[child/2] = a[child];
			child *= 2;
		}

		a[child / 2] = temp;
	}
	printelements(a);
}

void heapSort(element a[], int n)
{
	int i, j;
	element temp;

	for (i = n / 2; i > 0; i--) {
		adjust(a, i, n);
	}

	for (i = n - 1; i > 0; i--) {
		temp = a[1];
		a[1] = a[i + 1];
		a[i + 1] = temp;

		adjust(a, 1, i);
	}
}

int main() {
	element a[12];
	a[1].key = 1343; a[2].key = 3466; a[3].key = 8567; a[4].key = 3684; a[5].key = 8932; a[6].key = 6734;
	a[7].key = 6588; a[8].key = 3574; a[9].key = 3689; a[10].key = 3687; a[11].key = 4563;
	
	heapSort(a, 11);

	return 0;
}