heapsort

heap.c

#include "library.h"

//중복없는 랜덤 숫자 생성 및 초기화
heap_t * initHeap() {

	heap_t * heap = (heap_t *)malloc(sizeof(heap_t));
	
	bool checkExist[MAX_NUM+1] = { false, };

	int i,temp;

	srand((unsigned)time(NULL));

	for (i = 1; i < MAX_ARR+1; ) {

		temp = makeRandom();

		if (checkExist[temp] == false) {
			checkExist[temp] = true;
			heap->arr[i] = temp;
			++i;
		}


	}

	heap->size = MAX_ARR;

	return heap;

}

void heapify(int arr[], int idx, int size) {

	int temp = idx;
	int right = 2 * idx + 1;
	int left = 2 * idx;


	if (((left < size) && (arr[left] > arr[temp])) || ((right < size) && (arr[right] > arr[temp]))) {
		if (arr[left] > arr[right]) temp = left;
		else temp = right;
	}
	
	
	if (temp != idx) {
		swap(&arr[idx], &arr[temp]);
		heapify(arr, temp, size);
	}


}

void buildHeap(int arr[], int size) {
	
	int i;

	for (i = size / 2; i > 0; i--) {
		heapify(arr, i, size);
	}
}

void heapSort(heap_t *heap) {


	int i;


	buildHeap(heap->arr,MAX_ARR);


	for (i = heap->size; i > 1; i--) {

		if (i == 2 && (heap->arr[1] < heap->arr[2])) break;

		swap(&(heap->arr[1]), &(heap->arr[i]));
 		heapify(heap->arr, 1, i-1);
	}

}

library.c

#include "library.h"

int makeRandom() {

	return rand() % (MAX_NUM + 1);
}

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

void printArr(int arr[]) {
	int i;
	
	for (i = 1; i < MAX_ARR+1; i++) {
		printf("%d ", arr[i]);
	}

	printf("\n");
}

library.h

#pragma once

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

#define MAX_ARR 20
#define MAX_NUM 100

typedef struct heap {
	
	int size;
	int arr[MAX_ARR+1];

}heap_t;

int makeRandom(void);
void swap(int *, int *);

heap_t * initHeap(void);
void heapify(heap_t *, int, int);
void buildHeap(int[], int);
void heapSort(heap_t *);

void printArr(int[]);

main.c

#include "library.h"



int main(void) {

	heap_t * heap = initHeap();

	printArr(heap->arr);

	heapSort(heap);

	printArr(heap->arr);


	return 0;
}