MergeSort

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

// 단순정렬 // 합병정렬   #include <stdio.h> int N; int arr[30000];   void simple_sort() {     int i, j, temp;     for (i = 0; i < N; i++) {         for (j = i + 1; j < N; j++) {             if (arr[i] > arr[j]) {             temp = arr[i];             arr[i] = arr[j];             arr[j] = temp;             }         }     }   }     void merge_sort(int s, int e) {     int i, j, k, m;     if (s >= e) return;     m = (s + e) / 2;     merge_sort(s, m);     merge_sort(m + 1, e);           // ******주의******     // k는 1이 아니라, s임!!     // (s부터 e까지 정렬하기 때문!!!!!     i = s; j = m + 1; k = s;         // 왼쪽 영역, 오른쪽 영역 끝 전까지 반복     // 왼쪽 영역과 오른쪽 영역 비교하면서 temp 배열에 배치하면서 정렬     // 남아있는 왼쪽, 오른쪽 영역을 temp배열에 담기     // temp 배열을 원본에 복사     int tmp[30000];     while (i<=m && j<=e) {         if (arr[j]>arr[i]) tmp[k++] = arr[i++];         else tmp[k++] = arr[j++];     }       while(i<=m) { // 왼쪽 영역이 영역 안쪽에 있는 경우 옮겨 담음         tmp[k++] = arr[i++];     }     while(j<=e) { // 오른쪽 영역이 영역 안쪽에 있는 경우 옮겨 담음         tmp[k++] = arr[j++];     }       for (i=s;i<=e;i++) arr[i] = tmp[i];     // ******주의******     // for 문 범위 주의하기!!! 정렬을 진행한 s~e까지만 담는다!   }   int main(int argc, char *argv[]) {     int i;     scanf("%d", &N);     for (i = 0; i<N; i++) {         scanf("%d", &arr[i]);     }     merge_sort(0, N - 1);       for (i = 0; i < N; i++) printf("%d ", arr[i]);       return 0; } /**************************************************************     Problem: 2544     User: AXQ6548     Language: C     Result: Accepted     Time:18 ms     Memory:2952 kb ****************************************************************/