이번에는 힙 정렬 알고리즘을 구현해 보기로 해요.
힙 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
초기 힙 구성
루트와 맨 마지막 자손 교환
n을 1 감소
반복(n: n->1)
힙 구성
루트와 맨 마지막 자손 교환
n을 1 감소
초기 힙 구성(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
반복(i:1->n)
j:=1
반복(j>0)
pa:=PARENT(j)
조건: compare(base[j], base[pa])이 0보다 크면
base[j], base[pa] 교환
j: = pa
아니면
내부 루프 탈출
힙 구성(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
반복
lc:= LCHILD(me)
rc:= RCHILD(me)
자식이 없으면
탈출
조건 왼쪽 자식만 있을 때
조건 compare(base[me],base[lc])>0일 때
base[me], base[lc] 교환
탈출
bc := 왼쪽 자식과 오른쪽 자식 중에 자료가 큰 값의 인덱스
조건 compare(base[bc],base[me])>0일 때
base[bc],base[me] 교환
아니면
탈출
참고로 2.1.2에서 공통으로 사용할 코드를 이용하세요.
먼저 인덱스를 계산하는 매크로 상수를 정의하세요.
#define LCHILD(me) (2*me +1) #define RCHILD(me) (LCHILD(me)+1) #define PARENT(me) ((me-1)/2)
먼저 초기 힙을 구성해야 합니다. 초기 힙은 인덱스 1에서 마지막까지 순차적으로 초기 힙을 구성합니다.
template <typename data, typename compare>
void heap_sort(data *base, size_t n, compare algo)
{
for( size_t i =1 ; i<n; i++)
{
힙 구성에 참가할 자료는 부모와 비교하면서 교환이 반복할 수 있습니다. 그리고 그 과정에서 인덱스 값이 변할 수 있으므로 별도의 변수에 설정하여 사용하세요.
int j=i;
힙 구성에 참가할 자료를 부모와 비교하면서 교환을 반복할 때 루트까지 오면 더 이상 비교하지 않습니다.
while(j>0)//루트가 아니면 반복
{
먼저 자신의 부모 인덱스를 구하세요.
int pa = PARENT(j);//부모 인덱스를 구하기
만약 부모의 자료보다 더 크면 부모와 자료를 교환하고 인덱스를 부모의 인덱스로 변경합니다.
if( algo(base[j], base[pa]) >0 ) //부모보다 크면
{
swap(base[j],base[pa]);//부모와 교환
j = pa;
}
만약 부모의 자료보다 크지 않다면 힙을 구성한 것이므로 반복문을 탈출합니다.
else
{
break;
}
}
}
초기 힙 구성이 끝나면 루트와 마지막 자손의 자료를 교환하고 정렬할 범위를 1줄입니다.
swap(base[0],base[n-1]);//루트와 마지막 자손 교환
n--;
size_t me;
size_t lc;
size_t rc;
이후에 힙 구성은 정렬할 범위가 1이 되기 전까지 반복합니다.
while(n>1)//반복: n이 1보다 크면
{
원래 마지막 자손이었지만 루트의 자료와 교환하여 현재 루트인 자료가 있어야 할 위치를 찾아야 합니다. 따라서 현재 자신의 인덱스를 0으로 설정하세요.
me = 0;
자신의 위치를 찾을 때까지 반복합니다.
while(1)
{
자신의 왼쪽 자식과 오른쪽 자식의 인덱스를 구하세요.
lc = LCHILD(me);
rc = RCHILD(me);
만약 왼쪽 자식의 인덱스가 n보다 크거나 같으면 자식이 없는 것이므로 반복문을 탈출하세요.
if(lc>=n)//자식이 없음
{
break;
}
만약 rc가 n이면 왼쪽 자식만 있다는 것입니다.
if(rc == n)//왼쪽 자식만 있음
{
왼쪽 자식이 자신보다 더 크면 자료를 교환하세요.
if(algo(base[me], base[lc])<0)
{
swap(base[me],base[lc]);
}
자신의 왼쪽 자식만 있었으므로 교환한 위치의 자식은 없으니 반복문을 탈출하세요.
break;
}
둘 다 있을 때는 왼쪽 자식과 오른쪽 자식 중에 큰 자식의 인덱스를 먼저 구하세요.
int bc = lc;
if(algo(base[lc], base[rc])<0)
{
bc = rc;
}
자신과 비교하여 자식이 크면 자료를 교환하고 자식의 인덱스로 변경하세요.
if(algo(base[bc],base[me])>0)
{
swap(base[bc],base[me]);
me = bc;
}
만약 자식이 더 크지 않다면 힙을 구성한 것이므로 반복문을 탈출하세요.
else
{
break;
}
}
힙 구성이 끝나면 루트와 마지막 자손의 자료를 교환한 후에 정렬 범위를 1 줄입니다.
swap(base[0],base[n-1]);//루트와 마지막 자손 교환
n--;
}
}
테스트 코드도 2.1.3에서 작성한 코드에서 sequential_sort 부분을 heap_sort로 변경하세요.
#define MAX_DATA 1000
int main()
{
Member *base[MAX_DATA];
//퀵 정렬이 잘 동작하는지
//10개 원소를 번호 순으로 정렬하여
//확인하고 이름 순으로 정렬하여 확인하세요.
MakeRandomMembers(base,10);
cout<<"정렬 전"<<endl;
ViewMembers(base,10);
quick_sort(base,10,CompareByNum);
cout<<"번호로 정렬 후"<<endl;
ViewMembers(base,10);
quick_sort(base,10,CompareByName);
cout<<"이름으로 정렬 후"<<endl;
ViewMembers(base,10);
RemoveMembers(base,10);
//그리고 MAX_DATA 개일 때 수행 속도와
//MAX_DATA/10 개일 때 수행 속도를 비교해 보세요.
clock_t st,et;
MakeRandomMembers(base,MAX_DATA);
cout<<"수행 성능 테스트1 자료 개수:"<<MAX_DATA<<endl;
st = clock();
quick_sort(base,MAX_DATA,CompareByName);
et=clock();
cout<<"수행 속도:"<<et-st<<endl;
RemoveMembers(base,MAX_DATA);
MakeRandomMembers(base,MAX_DATA/10);
cout<<"수행 성능 테스트2 자료 개수:"<<MAX_DATA/10<<endl;
st = clock();
MakeRandomMembers(base,MAX_DATA/10);
quick_sort(base,MAX_DATA/10,CompareByName);
et=clock();
cout<<"수행 속도:"<<et-st<<endl;
RemoveMembers(base,MAX_DATA/10);
return 0;
}
▷ 실행 결과
정렬 전 0000757147,이름0167851000 0301413356,이름0336971124 0659598368,이름0160567225 0391749387,이름0004890851 0035766290,이름0026239572 0473038164,이름0000597006 0003615544,이름0326051436 0392289610,이름0118341522 0170427798,이름0037215528 0675016433,이름0168544290 번호로 정렬 후 0000757147,이름0167851000 0003615544,이름0326051436 0035766290,이름0026239572 0170427798,이름0037215528 0301413356,이름0336971124 0391749387,이름0004890851 0392289610,이름0118341522 0473038164,이름0000597006 0659598368,이름0160567225 0675016433,이름0168544290 이름으로 정렬 후 0473038164,이름0000597006 0391749387,이름0004890851 0035766290,이름0026239572 0170427798,이름0037215528 0392289610,이름0118341522 0659598368,이름0160567225 0000757147,이름0167851000 0675016433,이름0168544290 0003615544,이름0326051436 0301413356,이름0336971124 수행 성능 테스트1 자료 개수:1000 수행 속도:132 수행 성능 테스트2 자료 개수:100 수행 속도:9