02-Divide_and_Conquer_분할정복

큰 배열이  있으면

이걸 반쪼가리 낸다. (divide)

정렬되어있어야 계산하기 편하니까

정렬 할 수 있을 만큼의 크기가 되어야 한다.

그러니까

반쪼가리 또 낸다.(divide)

그걸 계속 반복하다보면

한칸단위로 나오게 된다. 한칸은 정렬(conquer)할 필요가 없기에 컴터가 딱보면 안다.

그럼 이제 크기비교를 해가면서 합치면 된다.(merge)

그렇게 다 비교해가면서 합치면(merge)

해결이 된다.

https://www.onlybook.co.kr/entry/algorithm-interview

여야 하는데...

배열여러개 만들면 복잡하기에 그냥 커다란 한 배열로 해서 

원래 배열

새 배열

이렇게 코드를 작성했습니다.

19부터 0까지 역으로 가져다 놓은걸 자기가 알아서 잘 세서 0부터 19까지 오름차순으로 해주는 코드 입니다.

#include <iostream>
using namespace std;
int *sorted;

void merge(int arr[], int left, int mid, int right){
    int i , j , k;
    i = left;
    j = mid + 1;
    k = left;

    while(i <= mid && j <= right){
        //첫번째배열이 배열중간의 끝까지 오거나
        //두번째배열이 우측끝까지 갈 때 까지 반복

        if(arr[i] <= arr[j]){
            //첫번째배열값들이 두번째배열보다 작아서 
            //첫배열값들 다 소모하면 그다음부턴 그냥 i 이후
            //부터 세는 경우
            sorted[k++] = arr[i++];
        }
        else{
            //그게 아니면 두번째 배열만큼입니다.
            sorted[k++] = arr[j++];
        }

    }
    if(i > mid){ //만약 배열1이 가운데보다 클 경우엔
        for(int x = j; x <= mid ; x++){ 
            sorted[k++] = arr[x];
            //두번째 배열만 보면 될듯합니다.
        }
    }
    else{
        //아님말고
        for(int x = i; x <= mid; x++){
            sorted[k++] = arr[x];
        }
    }
    //sorted의 left 부터 right 까지 모두 정렬된 상태인 경우
    for(int x = left; x <= right; x++){
        arr[x] = sorted[x];
        //다시원래 배열로 재 복사
    }
}

void mergesort(int arr[], int left, int right){
    //left right는 이 배열에서 보고 있는 범위
    int mid;
    if(left < right){
        //한칸짜리가 들어오면 거짓. 두칸부터 merge
        mid = (left + right)/2; //중간잡고
        mergesort(arr, left, mid);
        mergesort(arr, mid+1, right); //가운데는 ㄴㄴ
        merge(arr,left, mid, right);
    }
}
int main(){
    int arr[20] = {19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0};
    sorted = new int[20]();
    mergesort(arr,0,19);
    for(int i = 0; i < 20; i++){
        cout << arr[i] << " ";
        //최대한 endl은 적게. 속도 저하의 주범임.
    }
    delete[] sorted;
    return 0;
}

실행결과