Merge, Merge Sort

합병 정렬, 합병...

걍 머지는 이해했는데 머지 소트가 ^_ㅠ 하 

우선 외운다 ㅋㅋㅋㅋㅋ

Merge : 

#include <stdio.h>

// 백준17728번
int N, M;
int a[1000100];
int b[1000100];

int main(void) {

    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) { scanf("%d", &a[i]); }
    for (int i = 0; i < M; i++) { scanf("%d", &b[i]); }

    int i, j;
    i = j = 0;

    // 비교 할거 다하고~
    while ( (i < N) && (j < M) ) {
        if ( a[i] >= b[j] ) printf("%d ", b[j++]);
        else printf("%d ", a[i++]);
    }

    while(i < N) printf("%d ", a[i++]);
    while(j < M) printf("%d ", b[j++]);

    return 0;

}

Merge Sort:

#include <stdio.h>

int N;
int b[1000100];

void merge(int *a, int start, int end) {
    int mid, i, j, k;

    mid = (start+end) >> 1; // 절반으로 나눈다.
    i = start; // 왼쪽의 가장 낮은 index
    j = mid +1; // 오른쪽의 가장 낮은 index
    k = 0; // 임시 배열의 index

    while( i <= mid && j <= end) {
        if (a[i] <= a[j]) b[k++] = a[i++]; // 왼쪽 오른쪽 비교해서 작은것부터 복사
        else b[k++] = a[j++];
    }
    while (i <= mid) b[k++] = a[i++];
    while (j <= end) b[k++] = a[j++];

    for ( i = start; i <= end; i++) {
        a[i] = b[i -start]; // b를 다시 a로 copy. 
    }
}

void sort(int *a, int start, int end) {
    int mid;
    if ( start >= end ) return;

    mid = (start + end ) >> 1;
    sort(a, start, mid);
    sort(a, mid + 1, end);
    merge(a, start, end);
}


int main(void) {

    //int a[] = {10, -2, 5,4,3,7,10,-2,1,-3};
    int a[] = {10, -2, 5,4,-3,};
    int length = sizeof(a) / sizeof(int);
    sort(a, 0, length -1);
    //for (int i = 0; i < length; i++) printf("%d\n", b[i]);

    return  0;
}

 

 

참고 페이지:

https://travelerfootprint.tistory.com/83

합병 정렬(merge sort) C언어

https://travelerfootprint.tistory.com/82

백준 알고리즘 2751번: 수 정렬하기 2 C언어 합병 정렬(merge sort)