|
로터스 님이 쓰신 글 :
: 힙 정렬을 만들고 컴파일 해봤는데
: 아무래도 무한 루프에 빠진 듯 싶습니다.
: 적어도 메인함수의 printf() 문은 실행이 되어야 할 것 같은데
: 아무것도 안나오네요..
: 원인을 잘 모르겠습니다.
: 무엇이 잘못되었는지 가르켜주시면 고맙겠습니다~!
:
: ※파일 첨부 하였구요, 비주얼 C에서 컴파일 해보았습니다.
아래 소스는 제가 몇년전에 구현해본 것입니다.
님이 구현하신 것과 비교분석해 보시면 문제점을 발견하실 수 있을 거라 사료됩니다.
아래는 보통 문자열이나 기타 객체를 정렬할 때 사용할 수 있는 것입니다.
숫자를 정렬하려면
void **list를 int list[]로
void *ex를 int ex로
void *pmax를 int pmax로
바꾸면 됩니다.
물론 MakeMaxHeap와 RebuildMaxHeap를 호출할 때 전달하는 list도 당연히 지금과는 달라야겠습니다.
#include <stdlib.h>
#include <string.h>
int Compare(void *item1,void *item2);
void MakeMaxHeap(void **list,int count,int (*compare)(void *, void *));
void RebuildMaxHeap(void **list,int count,int (*compare)(void *, void *));
void HeapSortAsc()
{
#define ITEM_COUNT 20
char *strs[ITEM_COUNT]={NULL,};
randomize();
int i,j,n;
//테스트용 자료 만들기
for(i=0 ;i<ITEM_COUNT ;i++){
n = random(10) + 1;
strs[i] = new char[n+1];
for(j=0 ; j<n ;j++){
strs[i][j] = 'A' + random(26);
}
strs[i][n]='\0';
}
//정렬
MakeMaxHeap((void**)strs,ITEM_COUNT,Compare);
RebuildMaxHeap((void**)strs,ITEM_COUNT,Compare);
//이시점에서 정렬된 자료를 이용
//
//
//테스트를 위해 할당한 메모리 해제
for(i=0 ;i<ITEM_COUNT ;i++){
if(strs[i]) delete strs[i];
}
}
//---------------------------------------------------------------------------
//MakeMaxHeap과 RebuildMaxHeap에 전달한 list의 실제 형이 무엇이냐에 따라
//함수 내부의 비교 알고리즘이 달라져야 함.
//지금 예에서는 문자열이므로 지금과 같이 비교함.
int Compare(void *item1,void *item2)
{
return strcmp((char*)item1,(char*)item2);
}
//---------------------------------------------------------------------------
//초기의 최대힙을 구축
//list: 포인터를 원소로 갖는 일차원 배열을 가리키는 포인터
//count: 위 배열의 원소 갯수
//compare : 두 원소의 대소를 판단하는 함수를 가리키는 포인터
//배열의 인덱스는 0~count-1
void MakeMaxHeap(void **list,int count,int (*compare)(void *, void *))
{
register me,down;
void *ex;
int left,right;
if(!list || !compare) return;
for(me=(count-2)/2 ;me>=0 ; me--)
{
down=me;
// 자손들과 자신을 비교하여 자손 보다 작으면 서로 교체
while(true)
{
// 두 자식 중 큰 쪽과 자신을 비교하여 자식 보다 작으면 서로 교체
// 자식 보다 크면 탈출
left=down*2+1;
right=left+1;
if(left<count)
{
if(right<count)
{
if(compare(list[left],list[right])>0) down=left;
else down=right;
}
else
{
down=left;
}
if(compare(list[(down-1)/2],list[down])<0)
{
ex=list[(down-1)/2];
list[(down-1)/2]=list[down];
list[down]=ex;
}
else
{
break;
}
}
// 더 이상 자식이 없으면 탈출
else
{
break;
}
}// while(true) loop
} // for(me) loop
}
//---------------------------------------------------------------------------
//원소의 이동과 더불어 최대힙 재구축
//루트노드에 최대 값이 오게 되는데 그 즉시 제거하여 아래쪽으로 이동시킴->이 것을 반복해서 작업(오름차순정렬이 됨)
//list: 포인터를 원소로 갖는 일차원 배열을 가리키는 포인터
//count: 위 배열의 원소 갯수
//compare : 두 원소의 대소를 판단하는 함수를 가리키는 포인터
//배열의 인덱스는 0~count-1
void RebuildMaxHeap(void **list,int count,int (*compare)(void *, void *))
{
register me;
void *pmax;
int left,right;
if(!list || !compare) return;
while(count>1)
{
pmax=list[0];
me=0;
// 두 자식 중 큰 쪽을 상위 수준으로 올리고
// 그 쪽 부분 트리를 최대힙으로 다시 구축
while(true)
{
// 두 자식 모두 있을 때 큰 쪽을 상위 수준으로 올림
left=me*2+1;
right=left+1;
if(right<count)
{
if(compare(list[left],list[right])>0)
{
list[me]=list[left];
me=left;
}
else
{
list[me]=list[right];
me=right;
}
}
// 왼쪽자식밖에 없을 때 그 것을 상위 수준으로 올림
else if(left<count)
{
list[me]=list[left];
me=left;
}
// 위의 코드 보다 1회전 더 해야 아래에 해당되게 됨.
// 더 이상 자식이 없으면 리스트의 마지막 자료를
// me로 옮기고 부분 최대힙을 다시 만든다.
// 마지막 위치에 루트노드 자료(현재 트리에서 가장 큰 값)를 저장한 후
// 자료수를 1 감소시킴. 루프를 탈출.
else // (me<count && me*2+1>=count) 상황. 즉, 단말 노드.
{
if(me==count-1)
{
list[--count]=pmax;
break;
}
list[me]=list[count-1];
list[--count]=pmax;
// list[count-1]를 list[me]로 옮긴데 따른 부분 트리 재 구성
pmax=list[me];
while(me>0)
{
if(compare(list[(me-1)/2],pmax)<0)
{
list[me]=list[(me-1)/2];
me=(me-1)/2;
}
else
{
list[me]=pmax;
break;
}
}
break; // break while(true) loop
}// else block
} // while(true) loop
}// while(count>1) loop
}
//---------------------------------------------------------------------------
|
