[C++][구현] 힙 정렬 (Heap Sort)

⭐ 힙 정렬 (Heap Sort)

 

우선 힙이란 자료구조에 알고 있다고 가정하고, 진행하겠습니다.

 

진행과정

1. 정렬하고 싶은 배열을, heapify를 시켜줘서, MaxHeap을 만듭니다.

2. Heap의 0번째 노드인 Max값을 정렬된 배열의 마지막 인덱스에 저장해줍니다.

3. Heap의 0번째 노드에, 끝의 노드를 복사해줍니다.

4. Heap의 length - 1 값을 대상으로 다시 heapify 해줍니다.

5. 2번과정의 마지막 인덱스-1 을 대상으로 복사 시켜주며 2~4 과정을 반복해줍니다.

---

#include <iostream>
using namespace std;

void swap(int nums[], int length, int rootIdx) {
	int largeIdx = rootIdx;
	int leftChild = 2 * rootIdx + 1;
	int rightChild = 2 * rootIdx + 2;

	if (leftChild < length && nums[leftChild] > nums[largeIdx])
		largeIdx = leftChild;

	if (rightChild < length && nums[rightChild] > nums[largeIdx]) 
		largeIdx = rightChild;
	
	if (largeIdx != rootIdx) {
		int tmp = nums[largeIdx];
		nums[largeIdx] = nums[rootIdx];
		nums[rootIdx] = tmp;
		
		// recursive
		swap(nums, length, largeIdx);
	}
}

void heapify(int nums[], int length) { // make_heap
	for (int i = (length - 1)/ 2; i >= 0; i--) {
		swap(nums, length, i);
	}
}

void heapSort(int nums[], int sorted[], int length) {
	heapify(nums, length);

	for (int i = length-1; i >=0 ; i--) {
		
		// 끝 번호와 바꿔주기
		
		sorted[i] = nums[0];
		nums[0] = nums[i];
		heapify(nums, i);
	}
}

int main() {

	int nums[7] = { 4, 6, 3, 2, 7, 9, 1 };
	int sorted[7];

	heapSort(nums , sorted, 7);

	for (int i = 0; i < 7; i++) {
		cout << sorted[i] << ' ';
	}

}

---

 

 Heap sort는 시간복잡도는 O(nlgn)이고 unstable한 정렬 방법입니다.