merge sort

Programming/Algorithm 2018. 8. 24. 14:42 Posted by gaeddong2
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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 50
 
void tracer(int num[], int len){
    int i;
    for (i = 0; i<len; i++){
        printf("%d ", num[i]);
    }
    printf("\n\n");
}
void merge(int arr[], int start, int middle, int end)
{
    int i = start;
    int j = middle + 1;
    int k = start;
    int tmp[MAX];
    int idx = 0;
    while (i <= middle && j <= end)
    {
        if (arr[i] < arr[j])
        {
            tmp[k++= arr[i++];
        }
        else 
            tmp[k++= arr[j++];
    }
    while (i <= middle)
        tmp[k++= arr[i++];
    while (j <= end)
        tmp[k++= arr[j++];
 
    for (idx = start; idx <= end; idx++)
        arr[idx] = tmp[idx];
}
void mergesort(int arr[], int start, int end)
{
    if (start < end)
    {
        int middle = (start + end/ 2;
        mergesort(arr, start, middle);
        mergesort(arr, middle + 1end);
        merge(arr, start, middle, end);
    }
}
int main(void)
{
    int data[MAX];
    int i = 0;
 
    srand(time(NULL));
    for (i = 0; i < MAX; i++)
    {
        data[i] = rand() % 999 + 1;
    }    
    tracer(data, MAX);
    printf("\n\r");
    mergesort(data, 0, MAX -1);
    tracer(data, MAX);
    return 0;
}
cs


'Programming > Algorithm' 카테고리의 다른 글

필승 전략 게임 (Sprague–Grundy theorem)  (0) 2018.06.05
투 포인터 알고리즘  (0) 2018.05.02
DFS을 이용한 순열구하기  (0) 2018.04.09
순열 및 조합 참고 링크  (0) 2018.04.02
[자료구조] TRIE 예제 코드  (0) 2017.12.06