최대힙을 이용해서 제자리 정렬하기

힙정렬 수행시간이 O(n logn) // 합병 퀵보다 빠름 O(n^2) 

후기

1. 전역변수를 정확히 통제한다면 쓰는 건 나쁜 것 같지 않음. 아직 코드가 단순해서 그런 걸 수 있지만..

2. 간단한 것도 논리 정리하고 들어가는게 나음. 논리 간단한 것들은 어짜피 정리하는데에 시간도 얼마 안걸림. 

쉽다고해서 그냥 코딩하다가 시간 꼬인 감이 있음.

3. 다시 할 것 같진 않지만... 시간되면 전역 변수 없이 코드를 구성하기.(예상하건데 사실상 함수 인자들이  더러워지고, 노가다작업 일 거 같음. 못해서 안하는게 아님.. 아마도..) 

#include


int A[101] ={-1, 0};
int N = 0;
int size = 0;   // 다운힙에 last 안넣으려고.

void insertItem(int key);
void upHeap(int a);
int deleteItem();
void downHeap(int i);

void inplaceHeapSort();
void buildHeap();

void main()
{
	

	/*for(int i =0 ; i<=101; i++)
	{
		printf(" %d",A[i]);
	}*/

	

	int key;
	int heap_max;

	
	
	inplaceHeapSort();

	for(int i=1; i<=size; i++)
	{
		printf(" %d",A[i]);
	}
	

}



void insertItem(int key)
{
	
	
	if(N>100)
		printf("size error\n");

	A[N+1] = key;
	N++;

	upHeap(N);
}


void upHeap(int a)
{
	if(a==1)
		return;

	int parent = a/2;
	int temp=0;

	if(A[a]<= A[parent])
		return;
	else
	{
		temp = A[a];
		A[a] = A[parent];
		A[parent] = temp;
		upHeap(parent);
	}
}


int deleteItem()
{
	int max = A[1];
	A[1] = A[N];
	A[N] = 0;
	N--;
	
	downHeap(1);

	return max;
}


void downHeap(int i)
{

	for(int i=1; i<=size; i++)
	{
		printf(" %d",A[i]);
	}
	printf("\n"); // test용
	int l=2*i; //왼쪽 자식
	int r=2*i+1;  // 오른쪽 자식
	
	int temp;

	if(l>N)        // i 의 자식이 둘다 없는 경우
		return;      
	if(r>N)         // i의 자식이 왼쪽 하나인 경우
	{
		if(A[l]<=A[i])
			return;
		else 
		{
			temp=A[l];
			A[l] = A[i];
			A[i] = A[temp];
			return;
		}
	}
	 // 자식이 둘다 있는 경우
	if(A[i]>=A[l] && A[i]>=A[r])  //두 자식이 모두 부모보다 작음 
		return; 
	else                      // 둘중에 하나라도 크면 둘 중 큰 자식과 부모의 위치 바꾸기
	{
		if(A[l]< A[r])           
		{
			temp = A[r];
			A[r] = A[i];
			A[i] = temp;
			downHeap(r);
		}
		else
		{
			temp = A[l];
			A[l] = A[i];
			A[i] = temp;
			downHeap(l);
		}
	}
}


void inplaceHeapSort()
{
	
	int temp;

	buildHeap();
	size = N;

	/*for(int i=1; i<=size; i++)
	{
		printf(" %d",A[i]);
	}
	printf("\n");*/

	while(N>1)
	{
		temp = A[1];
		A[1] =A[N];
		A[N] = temp;
		N--;

		downHeap(1);
	}
}


void buildHeap()
{
	int n;
	scanf("%d", &n); 

	int key;
	for( int i = 1; i<=n; i++)
	{
		scanf("%d", &key);
		insertItem(key);
	}
}

--------------------------------------------------------------------------------- 

코딩하면서 노트

5 3 4 1 2    ---> 현재 출력 : 1 3 2 4 5 

5 3 4 1 2      

앞과 뒤 바꾸기(swap)

2 3 4 1 /5    

down

4 3 2 1 /5 

swap

1 3 2 /4 5           //여기서 계속 멈추는 거임.

down

3 1 2 /4 5  

swap

2  1 /345

// 가능성 1. 힙을 생성하는 부분이 잘못 되었다.

          2. 지금 추가적인 부분의 논리가 잘못 되었다.

2 가능성이 높음

ex)

 3 4 5 1 2   ---> 현재 출력 : 1 3 2 4 5 

//처음부터 설계 다시

builheap();

while(N>1){

A[1] <-> A[N];

downHeap(1);

}