티스토리 뷰

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
#include <cstdio>
 
void mergeSort(int n, int* array);
void merge(int h, int m, int* U, int* V, int* S);
 
int main() {
    int input;
    scanf("%d"&input);
    int* number = new int[input];
    for (int i = 0; i < input; i++)
        scanf("%d"&number[i]);
 
    mergeSort(input, number);
    for (int i = 0; i < input; i++)
        printf("%d\n", number[i]);
 
    delete[] number;
}
 
void mergeSort(int n, int* array) {
    if (n > 1) {
        const int h = n / 2;
        const int m = n - h;
 
        int* U = new int[h];
        int* V = new int[m];
 
        for (int i = 0; i < h; i++)
            U[i] = array[i];
        for (int i = 0; i < m; i++)
            V[i] = array[i + h];
 
        mergeSort(h, U);
        mergeSort(m, V);
        merge(h, m, U, V, array);
        delete[] U, V;
    }
}
 
void merge(int h, int m, int* U, int* V, int* S) {
    int i = 0, j = 0, k = 0;
    while (i < h && j < m) {
        if (U[i] < V[j]) {
            S[k] = U[i];
            i++;
        }
        else {
            S[k] = V[j];
            j++;
        }
        k++;
    }
    if (j < m)
        while (j < m)
            S[k++= V[j++];
    else
        while (i < h)
            S[k++= U[i++];
}
cs

nlgn인 정렬로 시간제한 통과할 수 있다고 써 있었는데, 그냥 퀵소트 돌려봤는데 시간초과 떴다.

그래서 머지소트 만들어서 통과시켰다.

댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/12   »
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
글 보관함