Merge Sort

https://dodo4513.github.io/2017/04/09/sort_2/

https://zeddios.tistory.com/38

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

Merge sort (합병 정렬)

  • 항상 nlogn 성능
  • 그러나 병합하는 과정에서 n사이즈 만큼의 메모리가 추가적으로 필요
  1. 리스트의 길이가 1이 될때까지 반으로 잘게 나눈다 -> Divide (분할정복)
  2. 다 나누어 졌다면, 데이터를 정렬하면서 합친다 -> Merge
#include <iostream>
using namespace std;
#define MAX_SIZE 8

int sorted[MAX_SIZE]; // 추가적인 공간이 필요

/*
tmpLeft : 정렬된 왼쪽 리스트에 대한 인덱스
tmpRight : 정렬된 오른쪽 리스트에 대한 인덱스
current : 정렬 될 리스트에 대한 인덱스
두개의 인접한 배열 list[left..mid]와 list[mid+1 .. right]의 병합 과정
*/
void merge(int list[], int left, int mid, int right){
    int tmpLeft = left;
    int tmpRight = mid + 1;
    int current = left;

    //분할 정렬된 list의 합병
    while (tmpLeft <= mid && tmpRight <= right){
        if (list[tmpLeft] <= list[tmpRight])
            sorted[current++] = list[tmpLeft++];
        else
            sorted[current++] = list[tmpRight++];
    }

    //남아 있는 값들을 일괄 복사
    if (tmpLeft > mid){ //오른쪽 리스트가 남음
        for (int i = tmpRight; i <= right; ++i)
            sorted[current++] = list[i];
    }
    else{//왼쪽 리스트가 남음
        for (int i = tmpLeft; i <= mid; ++i)
            sorted[current++] = list[i];
    }

    //배열 sorted[] (임시 배열)의 리스트를 배열 list[]로 재복사
    for (int i = left; i <= right; ++i)
        list[i] = sorted[i];
}

void merge_sort(int list[], int left, int right){
    int mid;

    if (left < right){
        mid = (left + right) / 2;
        merge_sort(list, left, mid);
        merge_sort(list, mid + 1, right);
        merge(list, left, mid, right); //정렬 된 2개의 부분 배열을 합병하는 과정
    }
}

void main(){
    int list[MAX_SIZE] = { 21, 10, 12, 20, 25, 13, 15, 22 };

    merge_sort(list, 0, MAX_SIZE-1); //left : 배열 시작, right : 배열 끝

    for (int i = 0; i < MAX_SIZE; ++i){
        cout << list[i] << endl;
    }
    
}

 

 

You may also like...