합병 정렬 : Merge Sort 내림차순으로 구현하기

합병 정렬 Merge Sort

---

성균관대학교 소프트웨어학과 조대호 교수님의 2020년도 2학기 알고리즘 수업을 듣고 수행한 과제입니다. 

배열을 내림차순으로 정렬하는 합병 정렬을 C로 구현하였습니다. 

• input and output conditions
  • Test the function with the following three types of integer inputs.
    1. int A[100] : filled with rand()%1000, execute srand(time(NULL)) first, (stdlib.h, time.h should be included) (Duplicate keys are ignored.)
    2. int A[100] : already sorted (Write a function for filling in A[])
    3. int A[100] : reversely sorted 
  • For the inputs of 2) and 3), A[] can be filled with the integers from 100 ~ 1 (from 100 down to 1) and 1 ~ 100 (from 1 to 100) respectively.
    1. Print A[], before and after sorting for each case of above inputs. 
        - Print the number of comparisons for each case of above inputs.

• source code 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int merge(int* A, int start, int mid, int end, int c) {

    int i = start;
    int j = mid + 1;
    int k = start;
    int B[100];

    while (i <= mid && j <= end) {
        if (A[i] <= A[j])
            B[k++] = A[j++];
        else
            B[k++] = A[i++];
        c++;
    }

    if (i > mid) {
        for (int t = j; t <= end; t++) {
            B[k++] = A[t];
        }
    }
    else {
        for (int t = i; t <= mid; t++)
            B[k++] = A[t];
    }

    for (int t = start; t <= end; t++) {
        A[t] = B[t];
    }


}

int merge_sort(int* A, int start, int end, int c) {
    c = 0;
    int middle;
    if (start < end) {
        middle = (start + end) / 2;
        merge_sort(A, start, middle, c);
        merge_sort(A, middle+1, end, c);
        c = merge(A, start, middle, end, c);
    }
    return c;
}



int print(int* A) {
    int i;
    for (i = 0; i < 100; i++) {
        printf(" %d", A[i]);
    }
    printf("\n");
    printf("\n");
    return 0;
}
int main() {
    int i;
    int count = 0;
    int A[100];

    printf("=============================================MERGE SORT=====================================================\n");

    /* (a) random */
    printf("(1) randomly filled array\n\n");
    srand(time(NULL));
    for (i = 0; i < 100; i++) {
        A[i] = rand() % 1000;
    }
    print(A);
    count = merge_sort(A, 0, 99, count);
    printf("after merge sorted\n\n");
    print(A);
    printf("number of comparison: %d\n", count);
    printf("============================================================================================================\n");

    /* (b) sorted */
    printf("(2) sorted array\n\n");
    for (i = 0; i < 100; i++) {
        A[i] = i+1;
    }
    print(A);
    count = merge_sort(A, 0, 99, count);
    printf("after merge sorted\n\n");
    print(A);
    printf("number of comparison: %d\n", count);
    printf("============================================================================================================\n");


    /* (c) reversly sorted */
    printf("(2) reversly sorted array\n\n");
    for (i = 0; i < 100; i++) {
        A[i] = 99 - i+1;
    }
    print(A);
    count = merge_sort(A, 0, 99, count);
    printf("after merge sorted\n\n");
    print(A);
    printf("number of comparison: %d\n", count);



    return 0;
}

• result

각 경우에 따른 합병 정렬에서 발생하는 comparsion operation 횟수는 다음과 같습니다. 

• 배열이 랜덤 값으로 채워진 경우 : 100
• 배열이 이미 정렬된 경우 : 100
• 배열이 반대로 정렬된 경우 : 100

다음 결과를 통해 합병 정렬에서는 주어진 배열의 상태와 상관없이 항상 비교 오퍼레이션 발생 횟수가 동일함을 알 수 있습니다. 즉, 어떤 상황에서도 유사한 성능을 낼 수 있는 정렬 알고리즘입니다.