5-2. 힙 정렬, 병합 정렬

1. 힙 정렬(Heap Sort)

힙의 특성을 이용한 정렬.

void HeapSort(vector<int>& v)
{
	priority_queue<int, vector<int>, greater<int>> pq; // 우선순위 큐를 내림차순으로 정렬

	for (int num : v) // 벡터 v의 모든 값을 우선순위 큐에 대입
		pq.push(num);

	v.clear();	// 벡터 v를 비움

	while (pq.empty() == false) // 우선순위 큐가 빌 때 까지
	{
		v.push_back(pq.top()); // 벡터 v에 우선순위 큐의 값을 작은 순서대로 집어넣음
		pq.pop();	// 우선순위 큐의 맨 위 데이터 제거
	}
}

우선순위 큐는 힙 구조로 되어있다.

우선순위 큐를 내림차순으로 정렬되어 있기 때문에 가장 작은 값이 우선순위 큐의 Top에 위치한다.

우선순위 큐의 Top의 값을 벡터에 하나 씩 집어넣어 정렬하는 구조이다.

 

 

 

2. 병합 정렬(Merge Sort)

분할 정복(Divide and Conquer)을 기조로 삼는다.

배열을 두 부분으로 나누어 각 부분을 정렬한 다음 합친다.

이후 다시 합쳐서 정렬한다.

이 과정을 재귀적으로 반복한다.

 

(1) 분할 (Divide)

문제를 작고 단순하게 분할한다.

전체 배열을 가장 작은 부분 배열로 쪼갠다.

원소가 하나인 부분 배열이 되면 분할이 끝난다.

void MergeSort(vector<int>& v, int left, int right)
{
	if (left >= right)
		return;

	int mid = (left + right) / 2;
	MergeSort(v, left, mid); // 왼쪽 절반의 배열을 쪼갬
	MergeSort(v, mid + 1, right); // 오른쪽 절반의 배열을 쪼갬

	MergeResult(v, left, mid, right); // 결합 함수
}

왼쪽 인덱스가 배열의 오른쪽 보다 크면 예외 처리로 함수를 종료한다.

left와 right를 더한 값을 2로 나눠 중앙 값을 mid에 저장하고

재귀적 호출을 통해서 왼쪽 절반 배열과 오른쪽 절반 배열을 가장 작게 쪼갠다.

 

(2) 정복 (Conquer)

분할된 작고 단순한 문제를 해결한다.

각 부분 배열을 정렬한다.

void MergeResult(vector<int>& v, int left, int mid, int right)
{
	vector<int> temp;

	int leftIdx = left;
	int rightIdx = mid + 1;

	while (leftIdx <= mid && rightIdx <= right)
	{
		if (v[leftIdx] <= v[rightIdx])
		{
			temp.push_back(v[leftIdx]);
			leftIdx++;
		}
		else
		{
			temp.push_back(v[rightIdx]);
			rightIdx++;
		}
		
        // 왼쪽의 정렬이 먼저 끝났으면 오른쪽 나머지 데이터를 복사
		if (leftIdx > mid)
		{
			while (rightIdx <= right)
			{
				temp.push_back(v[rightIdx]);
				rightIdx++;
			}
		}
        // 오른쪽의 정렬이 먼저 끝났으면 왼쪽 나머지 데이터를 복사
		else
		{
			while (leftIdx <= mid)
			{
				temp.push_back(v[leftIdx]);
				leftIdx++;
			}
		}
		for (int i = 0; i < temp.size(); i++)
			v[i] = temp[i];
	}
}

왼쪽 부분 배열의 인덱스인 leftIdx와 오른쪽 부분 배열의 인덱스인 rightIdx를 활용한다.

leftIdx가 두 부분 배열의 중앙값을 넘지 않고, rightIdx가 오른쪽 끝에 도달하지 않는 한 루프를 계속한다.

leftIdx = 0, rightIdx = 3

leftIdx = 1, rightIdx = 3

leftIdx = 1, rightIdx = 4

rightIdx = 5, leftIdx가 아직 mid(2)보다 작거나 같으므로 원소를 복사

leftIdx가 mid보다 크고, rightIdx가 right보다 크므로 루프 종료

(3) 결합 (Combine)

결과를 취합하여 정리한다.