1. HEAP SORT & MERGING SORT
    1. Heap Sort 힙 정렬
    2. Merge Sort 병합 정렬
    3. H3 중제목
    4. 마무리

글의 요약 설명 부분. 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

다른 글

다른 글 더 둘러보기

티스토리툴바