⭐ Programming/자료구조와 알고리즘
[알고리즘] Heap Sort, Merging Sort 힙 정렬, 병합 정렬
Designerd
2022. 11. 1. 16:00
글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자입니다
목차
HEAP SORT & MERGING SORT
본문내용넣기
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
int main()
{
vector<int> v{ 1, 5, 3, 4, 2 };
srand(time(0));
for (int i = 0; i < 50; i++)
{
int randValue = rand() % 100;
v.push_back(randValue);
}
//std::sort(v.begin(), v.end());
//HeapSort(v);
MergeSort(v, 0, v.size() - 1);
}
|
cs |
--recursive
📁build
Heap Sort 힙 정렬
시간 복잡도 NlogN
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
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();
}
}
|
cs |
Merge Sort 병합 정렬
시간 복잡도 NlogN
// 분할 정복 (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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
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);
}
|
cs |
H3 중제목
본문내용넣기
마무리
마무리
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <thread>
using namespace std;
// 힙 정렬
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
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);
}
int main()
{
vector<int> v{ 1, 5, 3, 4, 2 };
srand(time(0));
for (int i = 0; i < 50; i++)
{
int randValue = rand() % 100;
v.push_back(randValue);
}
//std::sort(v.begin(), v.end());
//HeapSort(v);
MergeSort(v, 0, v.size() - 1);
}
|
cs |