[자료구조] 21 합병정렬

📌합병 정렬 (Merge Sort)

✔️알고리즘

레코드 리스트를 반으로 나누어 2개의 서브리스트로 분할

또 분할.. 재귀적으로 분할.. 더 이상 분할 불가능 할 때까지

분할이 완료된 이후 이웃하는 두개의 파티션을 병합하여 정렬하는 방식

 

📌시간복잡도 : (nlog_2n)

✔️분할하는데 걸리는 시간 O(n)

✔️병합에 걸리는 시간 ( n + log_2n )

-두 서브 리스트 원소의 개수 s,t개라고 할 때 두 서브 리스트 병합에 걸리는 시간 n=s+t이므로 O(n)

-레벨의 수 (log_2n)

 

전체 레벨의 분할과 병합에 걸리는 시간 (nlog_2n)

 

합병 정렬

노트에다 막 쓴거라 깔끔하진 않으나.. 첨부 해본다

 

#include <stdio.h>
void mergesort(int num[], int left, int right);
void merge(int num[], int left, int mid, int right);
void print_array(int num[], int n);

void main(){
    int num[]= { 30,14,25,3,19,2,8,50 };
    print_array(num,8);
    mergesort(num,0,7); //수보다 한개 적게 right 설정 
}

void mergesort(int num[], int left, int right){
    int mid;
    if( right>left ){
        mid =( right+left )/2;
        mergesort(num, left, mid);
        mergesort(num, mid+1, right);
        //반 쪼개서
        merge(num, left, mid+1, right);
        print_array(num, 8);
    }
}

void merge(int num[], int left, int mid, int right){
    int i, left_end, num_items, pos;
    int temp[100]; //임시 배열을 이용

    left_end = mid-1;
    pos = left;
    num_items = right - left + 1; //파티션안의 몇개의 수가 있는지

    while((left <= left_end) && (mid <= right)){
        if(num[left] <= num[mid]){
            temp[pos] = num[left];
            pos = pos+1;
            left = left+1;
        }
        else{
            temp[pos] = num[mid];
            pos = pos+1;
            mid = mid+1;
        }
    }

    while(left<=left_end){
        //첫번째 세그먼트에 남아 있는 항목 추가
        temp[pos]=num[left];
        pos = pos+1;
        left = left+1;
    }

    while(mid<=right){
        //두번째 세그먼트에 남아 있는 항목 추가
        temp[pos] = num[mid];
        pos = pos+1;
        mid = mid+1;
    }

    for(i=0;i<num_items;i++){
        num[right] = temp[right];
        right = right-1;
    }
}

void print_array(int num[], int n){
    int i;
    for(i=0;i<n;i++){
        printf("%d ", num[i]);
    }
    printf("\n");
}
//결과
// 30 14 25 3 19 2 8 50 
// 14 30 25 3 19 2 8 50 
// 14 30 3 25 19 2 8 50 
// 3 14 25 30 19 2 8 50 
// 3 14 25 30 2 19 8 50 
// 3 14 25 30 2 19 8 50 
// 3 14 25 30 2 8 19 50 
// 2 3 8 14 19 25 30 50 

코드 자체가 길고 복잡해보여서 뜯어서 생각하기가 좀 귀찮았다..

다시 한번 확인하기 ❗️💢💢

 

❓floating point exception?

중간에 오류가 나고 찾아보니 0으로 나눴을 때 나는 오류였다

내가 mid = right+left 대신 mid = rifht/left 로 잘못 적어서 났던 오류