Algorithm
22 May 2020

stl 보다 10배빠른 merge sort

Merge sort

개요

  • 시간복잡도 : O(N*logN);

  • 병합정렬은 분할정복을 이용하며 계속 반으로 쪼개다가 1개만 남았을때 다시 합치는데 이때 오름차순이라면 작은게 먼저 버퍼에 들어가게 되며 구간의 병합이 끝났을때 버퍼에 있던 데이터를 원래의 데이터로 옮긴다.


int bufSize=10000// 정렬하고자하는 데이터의 크기에 맞춰 설정
int buf[bufSize];
void merge(int* p,int len){
    if(len<2)return;
    int i,j,k,mid;
    mid=len/2;
    i=0,j=mid,k=0;
    
    //분할
    merge(p,mid);
    merge(p+mid,len-mid);

    //병합
    while(i<mid&&j<len){
        if(p[i]<p[j]){
            buf[k++]=p[i++];
        }else{
            buf[k++]=p[j++];
        }
    }
    while(i<mid){
        buf[k++]=p[i++];
    }
    while(j<len){
        buf[k++]=p[j++];
    }
    
    //정렬된 버퍼의 데이터를 원본에 옮겨준다.
    for(int i=0;i<len;i++){
        p[i]=buf[i];
    }
}

int main(){
    int arr[5] = { 5,2,3,1,4 };
    for(int i=0;i<5;i++){
        cout<<arr[i]<<'\n';
    }
}

결과값

1 2 3 4 5
Tags:
0 comments