본문 바로가기
한국으로/알고리즘과 자료구조

병합 정렬 (Merge Sort)

by 영킴. 2018. 7. 4.

Merge Sort

Sample Code 1

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
void merge_sort(int s, int e)
{
    int idxtmp, idx1, idx2, m;
    
    if (s == e) return;
 
    m = (s + e) / 2;
 
    merge_sort(s, m);
    merge_sort(m + 1, e);
 
    idx1 = s, idx2 = m + 1, idxtmp = s;
 
    while (idx1 <= m && idx2 <= e)
    {
        if (index[idx1][0] &lt; index[idx2][0])
        {
            tmp[idxtmp][0] = index[idx1][0];
            tmp[idxtmp++][1] = index[idx1++][1];
        }
        else
        {
            tmp[idxtmp][0] = index[idx2][0];
            tmp[idxtmp++][1] = index[idx2++][1];
        }
    }
 
    if (idx1 <= m)
    {
        while (idx1 <= m)
        {
            tmp[idxtmp][0] = index[idx1][0];
            tmp[idxtmp++][1] = index[idx1++][1];
        }
    }
    else
    {
        while (idx2 <= e)
        {
            tmp[idxtmp][0] = index[idx2][0];
            tmp[idxtmp++][1] = index[idx2++][1];
        }
    }
 
    for (register int i = s; i <= e; i++)
    {
        index[i][0] = tmp[i][0];
        index[i][1] = tmp[i][1];
    }
 
}
 
cs


Sample Code 2

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
void merge_sort(int s, int e)
{
    int idxtmp, idx1, idx2, m;
 
    if (s >= e) return;
 
    m = (s + e) / 2;
 
    merge_sort(s, m);
    merge_sort(m + 1, e);
 
    idx1 = s; idx2 = m + 1; idxtmp = s;
 
    while (idx1 <= m && idx2 <= e)
    {
        if (arr[idx1] <= arr[idx2]) tmp[idxtmp++] = arr[idx1++];
        else tmp[idxtmp++] = arr[idx2++];
    }
 
    while (idx1 <= m) tmp[idxtmp++] = arr[idx1++];
    while (idx2 <= e) tmp[idxtmp++] = arr[idx2++];
    
    for (register int i = s; i <= e; i++) arr[i] = tmp[i];
}
 
cs


저작자표시 비영리 변경금지

'한국으로 > 알고리즘과 자료구조' 카테고리의 다른 글

힙 정렬 (Heap Tree Sort)  (0) 2018.07.03
세그먼트 트리 (Segment Tree)  (0) 2018.07.03

관련글

티스토리툴바