c) Heap 정렬을 해보자

안녕하세요 ㅎㅎ

이번은 힙정렬의 문제를 가지고 왔습니다.

우선 힙정렬을 한 후, k번째 작은 수를 찾는 알고리즘을 만들겠습니다.

배열은 랜덤함수를 이용하여 받았습니다.

코드입니다.

#include
#include
#include

#define swap(a,b)  {int t; t = a; a=b; b=t;} //a와 b를 교환, 자주 사용하기 때문에 정의하고 시작


void downHeap(int *l, int i, int n)   /// 마지막노드 이후는 계산 안하게 해야함.
{
	int *left = &l[2 * i + 1], *right = &l[(2 * i + 2)], *down, tmp; // 왼쪽 자식과 오른쪽 자식의 방의 위치 확인.

	if (2 * i + 2 < n)
	{
		if (*left < *right) {
			down = right;
			tmp = (2 * i) + 2;
		}
		else {
			down = left;
			tmp = (2 * i) + 1;
		}  // 자식 노드들 중 작은 값 = 내려갈 곳 , 그리고 그 방의 위치 기억

	} // 자식이 양쪽에 잇을 경우
	else {
		down = left; tmp = (2 * i) + 1;
	} // 자식이 왼쪽에만 있을 경우

	while (i >= 0)	// 내려갈 곳의 위치를 확인하였으니 스키탄다.
	{
		if (l[i] < *down) // l[i]가 부모
		{
			swap(l[i], *down);
			i = tmp; // 자리바꿈. 그리고 위치를 바꾼 위치로 갱신. 이를 반복
		}
		else break; // 부모가 자식보다 크게 되면 종료
	}
}




void buildHeap(int *l, int i, int n) // 힙 오름차순 정렬
{
	for (i = 0; i < n; i++)
	{
		swap(l[0], l[n - 1]); // root와 last 자리바꿈
		n--;	// 하나 빼고 다시하기 위해
		if (n == 1) return; // 1일땐 작동 안함,  이때는 이미 정렬도 되잇을테임
		for (i = (n - 2) / 2; i >= 0; i--)
			downHeap(l, i, n);	// 스키타기
	}
}



int findKthSmallest(int *l, int n)
{
	int i;

	for (i = (n - 2) / 2; i >= 0; i--)	// 비재귀적 상향식 힙생성. 
		downHeap(l, i, n); 
	buildHeap(l, i, n); // 힙정렬(오름차순)
	return 0;
}



void main()
{
	srand((unsigned)time(NULL));	// 시간에 따라 랜덤값 다르게 하기 위해서
	int i, n, arr[10000], k;	

	printf("리스트 크기: ");
	scanf("%d", &n); // 배열의 크기

	for (i = 0; i < n; i++)
		arr[i] = (int)(((double)rand() * 1000000 / (double)RAND_MAX + 1));  // 난수발생함수로 목록 값들 정함

	if (n < 99)
	{
		printf("리스트:"); // 리스트 크기가 100보다 작을때는 출력
		for (i = 0; i < n; i++)
			printf(" %d", arr[i]); // 난수발생함수 결과물 확인 
		printf("\n");
	}

	findKthSmallest(arr, n);
	for (i = 0; i<3; i++) // 3번 돌림
	{
		printf("순위: ");
		scanf("%d", &k);  // k값 설정
		printf("%d", *(arr + k - 1)); // k번째 값 출력. ( 앞에 있을 수록 작다.-오름차순 되있음 )
		printf("\n");
	}
}

실행 화면입니다.

간단하죠?

질문이나 지적 있으시면 부탁드릴게요!

더 좋은 프로그램으로 찾아오겠습니다 ㅎㅎ