[알고리즘] Heap Sort, Merging Sort 힙 정렬, 병합 정렬
글의 요약 설명 부분. 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 |
'⭐ Programming > 자료구조와 알고리즘' 카테고리의 다른 글
| [알고리즘] 이진 탐색(Binary Search), 이진 탐색 트리(Binary Search Tree) (0) | 2022.11.02 |
|---|---|
| [알고리즘] A* 길찾기 알고리즘 (0) | 2022.11.02 |
| [알고리즘] 정렬 Sorting (0) | 2022.11.01 |
| [알고리즘] 우선순위 큐 Priority Queue (0) | 2022.10.31 |
| [자료구조] 이진 트리, 힙 이론, 힙 트리 (0) | 2022.10.31 |
댓글
이 글 공유하기
다른 글
-
[알고리즘] 이진 탐색(Binary Search), 이진 탐색 트리(Binary Search Tree)
[알고리즘] 이진 탐색(Binary Search), 이진 탐색 트리(Binary Search Tree)
2022.11.02 -
[알고리즘] A* 길찾기 알고리즘
[알고리즘] A* 길찾기 알고리즘
2022.11.02 -
[알고리즘] 정렬 Sorting
[알고리즘] 정렬 Sorting
2022.11.01 -
[알고리즘] 우선순위 큐 Priority Queue
[알고리즘] 우선순위 큐 Priority Queue
2022.10.31