[알고리즘]분할 정복

분할 정복이란

문제를 더 이상 나눌 수 없을 때까지 나누고, 각각 문제를 풀어 다시 합치는 알고리즘

1. 분할 : 문제가 분할이 가능하다면 2개 이상의 하위 문제로 나눔

2. 정복 : 하위 문제가 분할이 가능하다면 다시 분할 

   가능하지 않다면 문제 풀이

3. 결합 : 정복에서 풀이 한 답을 정리

병합 정렬

나누고 합치는 정렬, 퀵 정렬을 기반이 되는 알고리즘

데이터의 집합이 2개 이상일 때까지 반으로 계속 나누고 각 크기를 비교하고 정렬 후 다시 결합하는 방식

C 소스

/*

* MergeSort.c

*

* Created on: 2019. 1. 12.

* Author: otrodevym

*/

#include <stdio.h>

#include <stdlib.h>

void MergeSort(int DataSet[], int StartIndex, int EndIndex);

void Merge(int DataSet[], int StartIndex, int MiddleIndex, int EndIndex);

void MergeSort(int DataSet[], int StartIndex, int EndIndex){

    int MiddleIndex;

    if(EndIndex - StartIndex < 1){

        return ;

    }

    MiddleIndex = (StartIndex + EndIndex)/2;

    MergeSort(DataSet, StartIndex, MiddleIndex);

    MergeSort(DataSet, MiddleIndex+1, EndIndex);

    Merge(DataSet, StartIndex, MiddleIndex, EndIndex);

}

void Marge(int DataSet[], int StartIndex, int MiddleIndex, int EndIndex){

    int i;

    int LeftIndex = StartIndex;

    int RightIndex = EndIndex;

    int DestIndex = 0;

    int* Destination = (int*)malloc(sizeof(int) * (EndIndex - StartIndex +1 ));

    while(LeftIndex <= MiddleIndex && RightIndex <= EndIndex){

        if(DataSet[LeftIndex] < DataSet[RightIndex]){

            Destination[DestIndex] = DataSet[LeftIndex];

            LeftIndex++;

        }else{

            Destination[DestIndex] = DataSet[RightIndex];

            RightIndex++;

        }

        DestIndex++;

    }

    while(LeftIndex <= MiddleIndex){

        Destination[DestIndex++] = DataSet[LeftIndex++];

    }

    while(RightIndex <= EndIndex){

        Destination[DestIndex++] = DataSet[RightIndex++];

    }

    DestIndex = 0;

    for(i = StartIndex; i <=EndIndex; i++){

        DataSet[i] = Destination[DestIndex++];

    }

    free(Destination);

}

int main(){

    int DataSet[] = {334, 6, 4, 2, 3, 1, 5, 117, 12, 34};

    int Length = sizeof(DataSet) / sizeof(DataSet[0]);

    int i = 0;

    MergeSort(DataSet, 0, Length-1);

    for(i = 0; i < Length; i++){

        printf("%d ", DataSet[i]);

    }

    printf("\n");

    return 0;

}

Java 소스

package m_divide_comquer;

public class MergeSort {

    private int[] data;

    private int[] temp;

    public MergeSort() {

    }

    public MergeSort(int[] arr) {

        data = arr;

        temp = new int[arr.length];

    }

    

    

    private void mergeSort(int startIndex, int endIndex) {

        if(endIndex > startIndex) {

        

        int middleIndex = (startIndex + endIndex) /2;

        

        mergeSort(startIndex, middleIndex);

        mergeSort(middleIndex+1, endIndex);

        

        

        merge(startIndex, middleIndex, endIndex);

        }

    }

    private void merge(int startIndex, int middleIndex, int endIndex) {

        for(int i = startIndex; i <= endIndex; i++) {

            this.temp[i] = this.data[i];

        }

        int leftIndex = startIndex;

        int rightIndex = middleIndex+1;

        

        int index = startIndex;

        

        while(leftIndex <= middleIndex && rightIndex <= endIndex) {

            if(this.temp[leftIndex] <= this.temp[rightIndex]) {

                this.data[index] = this.temp[leftIndex];

                leftIndex++;

            }else {

                this.data[index] = this.temp[rightIndex];

                rightIndex++;

            }

            index++;

        }

        

        for(int i =0; i <= (middleIndex-leftIndex); i++) {

            this.data[index + i] = this.temp[leftIndex +i];

        }

    }

    

    public static void main(String args[]) {

        int[] arr = {334, 6, 4, 2, 3, 1, 5, 117, 12, 34};

        MergeSort ms = new MergeSort(arr);

        

        ms.mergeSort(0, ms.data.length-1);

        

        for(int i = 0; i < ms.data.length; i++) {

            System.out.print( " " + ms.data[i]);

        }

        

    }

}