분할 정복 (병합정렬, 퀵정렬)

분할 정복 (Divide & Conquer)

주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산
=> 빠르게 작업을 처리할 수 있다

1. divide : 문제를 더 작은 문제로 분할하는 과정
2. merge : 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정
3. base case : 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제

• example : 1 + 2 + ... + n

  int sum(int n) {
    // 기저 사례
    if (n == 1) return 1;
    if (n % 2 == 1) return sum(n-1) + n;  // 홀수일 경우 처리 방법
    return 2*sum(n/2) + (n/2)*(n/2);

병합 정렬 (Merge sort)

주어진 수열을 가운데에서 쪼개 비슷한 크기의 수열 두 개로 만든 뒤 이들을 재귀 호출을 이용해 각각 정렬한다.
그 후 정렬된 배열을 하나로 합침으로써 정렬된 전체 수열을 얻는다.

// mergeSort({33, 27, 35, 4, 82, 3, 19}, 0, 6);
void mergeSort(int data[], int start, int end) {
    if (start >= end) return;
    
    //분할
    int mid = (start + end) / 2;
    mergeSort(data, start, mid);
    mergeSort(data, mid + 1, end);

    //병합
    int sortedData[10000];
    int leftPtr = start;
    int rightPtr = mid + 1;
    int tmpPtr = start;
    
    while ((leftPtr <= mid) && (rightPtr <= end)) {
        if (data[leftPtr] < data[rightPtr]) {
            sortedData[tmpPtr++] = data[leftPtr++];
        }
        else {
            sortedData[tmpPtr++] = data[rightPtr++];
        }
    }
    
    while (leftPtr <= mid) {
        sortedData[tmpPtr++] = data[leftPtr++];
    }
    while (rightPtr <= end) {
        sortedData[tmpPtr++] = data[rightPtr++];
    }

    for (tmpPtr = start; tmpPtr <= end; tmpPtr++) {
        data[tmpPtr] = sortedData[tmpPtr];
    }
}

출처 : https://hijuworld.tistory.com/48

시간복잡도 = O(NlogN)

퀵 정렬 (Quick sort)

병합 과정이 필요없도록 한쪽의 배열에 포함된 수가 다른 쪽 배열의 수보다 항상 작도록 배열을 분할한다.
~ 파티션 : 배열에 있는 수 중 임의의 기준수(pivot)를 지정한 후 기준보다 작거나 같은 숫자를 왼쪽, 더 큰 숫자를 오른쪽으로 보내는 과정

// quickSort({33, 27, 35, 4, 82, 3, 19}, 0, 6);
void quickSort(int data[], int start, int end) {
    if (start >= end) return;

    int pivot = start;
    int left = pivot + 1;
    int right = end;

    while (left <= right) {
        while (left <= end && data[left] <= data[pivot]) {
            left++;
        }
        while (right >= start && data[right] >= data[pivot]) {
            right--;
        }

        if (left > right) swap(data, pivot, right);
        else swap(data, pivot, left);
    }
    
    //분할 계산
    quickSort(data, start, right - 1);
    quickSort(data, right + 1, end);
}

void swap(int data[], int i, int j) {
    int tmp = data[i];
    data[i] = data[j];
    data[j] = tmp;
}

출처 : https://hongku.tistory.com/149

시간복잡도 = O(NlogN)