[알고리즘]힙정렬

힙정렬이다.. 우선 소스를 보자.

// 깊이를 구하기위해서 값이 1이하가 될 때까지 쉬프트 연산을 해

// 주고
// 쉬프트 연산의 회수를 반환
int Lg2(int iVal)
{
int temp = 0;
while(iVal > 1)
{
++temp;
iVal >>= 1;
}
return temp;
}

// root인덱스가 추가되었을 때 힙을 재구성해주는 함수
// 좌우 자식중 큰 값을 부모와 비교하여 부모가 크다면 그대로 두

// 고
// 자식이 크다면 부모와 바꿔준다.
// 만약 부모와 자식을 바꾸었다면, 내려간 부모의 인덱스를 이용해

// 다시 자신을 호출한다.
// 여기서 root는 최대 iVec.size() >> 1 즉 배열 크기의 절반이므

// 로
// 최소한 왼쪽 자식은 존재한다.
void LocalHeapify(vector & iVec, int root)
{
int max; // 두 자식중 큰 값의 인덱스를 저장할 변수
int leftChild = root * 2; // 왼쪽 자식
int rightChild = root * 2 + 1; // 오른족 자식
// 두 자식중 큰값의 인덱스를 max에 저장
if(rightChild != iVec.size()) // 오른쪽 자식이 배열의 크기와 같다

//면
// 오른쪽 자식은 배열의 인덱스를 벗어난 것이다.
{
iVec[leftChild] > iVec[rightChild] ? max = leftChild : max = rightChild;
}else
{
max = leftChild;
}

// 만약 자식이 부모보다 크다면 두 값을 바꿔주고
// 내려간 부모의 인덱스를 이용해 재귀적으로 호출
if(iVec[max] > iVec[root])
{
SwapInt(iVec[max], iVec[root]);
if(max <= (iVec.size() >> 1))
{
LocalHeapify(iVec, max);
}
}
}

// 들어온 배열로 힙을 만들어주는 함수
// 마지막 원소의 인덱스를 2로 나눈 것부터 첫번째 원소까지
// LocalHeapify함수를 호출
// 마지막 원소의 인덱스를 2로 나눈 것이 자식을 가지는 가장 아래

// 의 가장 오른쪽 원소이기때문이다.
void MakeHeap(vector & iVec)
{
int temp = (iVec.size() - 1) >> 1;
for(int i = temp; i > 0; --i)
{
LocalHeapify(iVec, i);
}
}

// 만들어진 힙을 사용해서 힙정렬을 수행하는 함수
// 루트를 마지막원소와 바꿔주는 연산을 계속하면서
// 바꿔준 뒤에 힙을 재구성하는 AcceleratedHeapify함수를 호출
void HSort(vector & iVec)
{
int end = iVec.size() - 1;
while(end > 1)
{
SwapInt(iVec[1], iVec[end]);
AcceleratedHeapify(iVec, --end);
}
}

// 루트의 바뀐 값을 이용해 힙을 재구성 하는 함수
// 깊이의 절반만큼 자식들만 비교해서 내려간뒤
// 들어온 값이 자신의 부모보다 크다면 위로 올라가면서 제자릴 찾

//고 끝내고
// 들오온 값이 자신의 부보보다 작다면 다시 남은 깊이의 절반만큼

//내려간다.
// 만약 리프까지 내려오면 종료한다.
void AcceleratedHeapify(vector & iVec, int end)
{
// 값이 1개도 남지않았다면 종료
if(end < cur =" 1;">

//다.
int treeHeight = Lg2(end); // 정렬되지 않은 트리의 깊이를 구한

//다.
int currentHeight = 0; // 들어온 값이 내려온 깊이를 저장한다.
// 리프까지 내려갈때까지 루프를 돈다.
while(currentHeight <= treeHeight) { int move = (treeHeight - currentHeight) / 2 + 1; // 한번에 내려

//갈 깊이
for(int i = 0; i <>

//내려간다.
{
int leftChild = cur * 2;
int rightChild = cur * 2 + 1;
int max;
if(leftChild > end)
{
break;
}else if(rightChild > end)
{
max = leftChild;
}else if(iVec[leftChild] > iVec[rightChild])
{
max = leftChild;
}else
{
max = rightChild;
}
SwapInt(iVec[cur], iVec[max]);
cur = max;
}
int parent = cur / 2;
if(cur > 1 && iVec[cur] > iVec[parent]) // 만약 내려간 위치에

//서 부모가 자신보다 작다면
{
while(cur > 1 && iVec[cur] > iVec[parent]) // 정확한 위치를

//찾을 때까지 거슬러 올라간다.
{
SwapInt(iVec[cur], iVec[parent]);
cur = parent;
parent = cur / 2;
}
return; // 정확한 위치를 찾았으니 종료
}
currentHeight += move; // 내려간 위치의 깊이를 저장
}
}

주석때문에 보기가 엉망이다... 거기다 힙정렬의 변화형을 사용했기때문에 소스가 길어졌다.

이 소스도 아래의 퀵정렬과 마찬가지로 전에 만들었던 소스를 그냥 올린 것이다.