[Sorting] Chapter 02. 힙 정렬과 병합 정렬

GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/2a955748fbaf3cbd0f5cf002a83f51d2bb347387

힙 정렬과 병합 정렬 · developeSHG/Data_Structure-Algorithm@2a95574

 

 

---

 

 

cpp

닫기 줄바꿈

#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
using namespace std;
#include <thread>
// 오늘의 주제 : 정렬

// C# 자료구조/알고리즘
// -> A* OpenList (PQ)
// -> C# List = C++ vector

// PQ O(logN)
// Red-Black Tree O(logN)
// Sorting ?

// 힙 정렬
// 힙 구조가 최소 혹은 최대에 해당하는 데이터를 뽑을 때, 가장 최적화되어있는 자료구조라는 것을 학습했었다.
// 대표적으로 PQ(우선순위 큐)
void HeapSort(vector<int>& v)
{
‌priority_queue<int, vector<int>, greater<int>> pq;

‌// O(NlogN)
‌for (int num : v)
‌‌pq.push(num);

‌v.clear();

‌// O(NlogN)
‌while (pq.empty() == false)
‌{
‌‌v.push_back(pq.top());
‌‌pq.pop();
‌}
}

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

// [3][K][7][2][J][4][8][9]			8개 * 1
// [3][K][7][2] [J][4][8][9]		4개 * 2
// [3][K] [7][2] [J][4] [8][9]		2개 * 4
// [3] [K] [7] [2] [J] [4] [8] [9]	1개 * 8
// [3][K] [2][7]  [4][J]  [8][9]	2개 * 4

vector<int> Merge(vector<int> a, vector<int> b)
{
‌vector<int> temp;

‌return temp;
}

// O(NlogN)
void MergeResult(vector<int>& v, int left, int mid, int right)
{
‌// [2][3][7][K][4][8][9][J]
‌//          [l]            [r]
‌int leftIdx = left;
‌int rightIdx = mid + 1;

‌// [2]
‌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);
}


int main()
{
‌vector<int> v;

‌srand(time(0));

‌for (int i = 0; i < 50; i++)
‌{
‌‌int randValue = rand() % 100;
‌‌v.push_back(randValue);
‌}

‌//HeapSort(v);

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