🙇‍♀️Sort2


🪐Sort2

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 힙 정렬
void HeapSort(vector<int>& v)
{
	priority_queue<int, vector<int>, greater<int>> pq;

	for (int num : v)
		pq.push(num);

	v.clear();

	while (pq.empty() == false)
	{
		v.push_back(pq.top());
		pq.pop();
	}
}

// 병합 정렬
// 분할 정복 (Divide and Conquer)
// - 분할 (Divide)		문제를 더 단순하게 분할한다
// - 정복 (Conquer)		분할된 문제를 해결
// - 결합 (Combine)		결과를 취합하여 마무리

void MergeResult(vector<int>& v, int left, int mid, int right)
{
	int leftIdx = left;
	int rightIdx = mid + 1;
	vector<int> temp;

	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[left + i] = temp[i];
}

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);
}


vector<int> Merge(vector<int> a, vector<int> b)
{
	int leftIdx = 0;
	int rightIdx = 0;
	vector<int> temp;

	while (leftIdx <= a.size() - 1 && rightIdx <= b.size() - 1)
	{
		if (a[leftIdx] <= b[rightIdx])
		{
			temp.push_back(a[leftIdx]);
			leftIdx++;
		}
		else
		{
			temp.push_back(b[rightIdx]);
			rightIdx++;
		}
	}

	// 한쪽 인덱스를 다 쓴 경우 나머지 복사
	if (leftIdx > a.size() - 1)
	{
		while (rightIdx <= b.size() - 1)
		{
			temp.push_back(b[rightIdx]);
			rightIdx++;
		}
	}
	else
	{
		while (leftIdx <= a.size() - 1)
		{
			temp.push_back(a[leftIdx]);
			leftIdx++;
		}
	}

	return temp;
}

int main()
{
	vector<int> v{ 1, 5, 3, 4, 2 };
	vector<int> w{ 10, 32, 45, 51, 70 };
	vector<int> x{ 12, 23, 42, 47, 63, 65, 80 };

	MergeSort(v, 0, v.size() - 1);

	for (int i : v)
		cout << i << endl;

	cout << endl;

	auto result = Merge(w, x);

	for (int i : result)
		cout << i << endl;
}

참고