처음으로 알고리즘에 대한 정리를 해보네요. 이번에 다룰 내용은 힙 정렬Heap Sort입니다!

원래 이것을 다루기 전에 버블 정렬Bubble Sort, 선택 정렬Selection Sort 등을 정리하는게 일종의 불문율(?)이긴 한데, 최근에 공부하고 이해한 것이 힙 정렬이라, 이것 먼저 다룰려고 합니다. 전 단계(?)들은 이후에 다루겠습니다.

힙 정렬

자료구조 중 하나인 힙 트리Heap Tree를 응용해서 정렬하는 방식입니다. 힙 트리를 누르시면 제가 정리한 내용이 있어요.

어떻게 응용하는가?

힙 트리의 특성과 최대 힙Max Heap을 응용합니다.

최대 힙의 Max Heap의 특성 중 하나인 루트 노드 값이 다른 노드들 중에 제일 큰 값이라는 점을 주목해주세요. 힙 정렬은 이러한 특성을 활용해 정렬을 수행해요.

1. 최대 힙으로 구성된 이진 트리의 루트 노드 값을 가장 뒤에 존재하는 노드와 값을 바꿉니다.
   1-1. 이 때 가장 큰 값은 가장 뒤로 위치하게 됩니다. 즉, 적절한 위치에 배치가 된 상태!
2. 가장 뒤에 있는 노드를 제외하고 힙을 재구성합니다.
3. 현 시점의 마지막 노드 인덱스보다 한 칸 아래쪽 노드와 루트 노드를 바꿉니다.
4. 1~3번을 0-base 기준 1번째 인덱스까지 반복합니다.

결국 최대 힙으로 구성되면 루트 노드가 가장 큰수라는 점을 활용해 해당 값을 가장 뒤로 위치시키고 그 원소를 제외하고 힙 트리 구성을 반복하다보면 정렬이 완성됩니다.

힙을 구성하는데 필요한 시간 복잡도는 $O(log n)$이니까 이를 n번 수행하므로 정렬의 시간 복잡도는 $O(nlogn)$입니다.

소스

template<typename T>
class HeapSort
{
public:
	static void sort(vector<T>& arr)
	{	
		int n = arr.size();
		
		cout << "Max Heap 초기화" << endl;
		for(int i = n / 2 - 1; i >= 0; --i)
			heapify(arr, n, i);

		cout << "추출 연산" << endl;
		for(int i = n - 1; i > 0; --i)
		{
			swap(arr[0], arr[i]);
			heapify(arr, i, 0);
		}
	}

private:
	static void heapify(vector<T>& arr, int n, int i)
	{
		int parent = i;
		int lChild = i * 2 + 1;
		int rChild = i * 2 + 2;

		// 좌측
		if(lChild < n && arr[parent] < arr[lChild])
			parent = lChild;
		// 우측
		if(rChild < n && arr[parent] < arr[rChild])
			parent = rChild;

		if(i != parent)
		{
			swap(arr[parent], arr[i]);
			print(arr);
			heapify(arr, n, parent);
		}
	}

};

실제로 활용하는가?

아쉽게도 아닙니다. 힙 정렬은 시간복잡도가 최선, 평균, 최악 모두 $O(nlogn)$인데다, 추가 메모리 할당도 없는 이론적으론 이상적인 알고리즘이긴 하나, 실제론 퀵 정렬Quick Sort을 사용합니다(최근엔 팀 정렬Tim Sort를 더 많이 채용하긴 합니다. 기회가 되면 다루도록 하겠습니다).

퀵 정렬은 평균적으로 $O(nlogn)$의 시간복잡도를 가지나, 최악의 경우 $O(n^{2})$입니다. 그럼에도 퀵 정렬을 더 많이 사용하는 이유는 컴퓨터의 참조 지역성 원리때문입니다.

참조 지역성 원리
CPU가 미래에 원하는 데이터를 예측하여 속도가 빠른 장치인 캐시 메모리에 담아 놓는데 이때의 예측률을 높이기 위하여 사용하는 원리이다. 쉽게 말하자면, 최근에 참조한 메모리나 그 메모리와 인접한 메모리를 다시 참조할 확률이 높다는 이론을 기반으로 캐시 메모리에 담아놓는 것이다. 메모리를 연속으로 읽는 작업은 캐시 메모리에서 읽어오기에 빠른 반면, 무작위로 읽는 작업은 메인 메모리에서 읽어오기에 속도의 차이가 있다. - 네이버 D2

쉽게 말씀드리자면 현재 현재 참조한 원소를 기준으로 인접 인덱스의 원소 접근은 캐시 메모리에 따로 저장되어 더 빠르게 접근할 수 있어요.

힙 정렬은 트리로 구성된 것을 전제로 하기 때문에 원소를 임의 접근하는 반면, 퀵 정렬은 인접한 원소를 접근하는 방식으로 전개되어 실제론 힙 정렬보다 빠른 처리 속도를 보여줍니다.

예전에 학교에서 배웠을 땐 막연히 퀵 정렬이 힙 정렬보다 빠르다고만 알고만 있었고 왜 그러는지를 몰랐었는데 이번에 정렬 개념을 리마인드하면서 배우게 되어, 여기다 남깁니다 ㅎㅎ. 한 단계 성장한 기분이 듭니다.

힙 정렬에 대한 내용은 여기까집니다. 나머지 정렬에 대한 개념은 추후에 다뤄야겠습니다.