16 일차

정렬과 탐색 (분할 정복과 정렬 알고리즘)

∙ 분할 정복 (divide and conquer)

- 주어진 문제의 규모가 커서 한 번에 해결하기 어려운 경우, 이를 작은 부분 문제로 나워서 해결하는 방식

- 분할(divide) : 주어진 문제를 동일한 방식으로 해결할 수 있는 부분 문제로 나누기

- 정복(conquer) : 각 부분 문제에 대한 솔루션 구하기

- 결합(combine) : 각 부분 문제의 솔루션을 결합하여 전체 문제에 대한 솔루션 구하기

 

∙ 분할 정복을 이용한 정렬 알고리즘

- 병합 정렬(merge sort)

> 분할 정복에 의한 정렬 알고리즘의 하나

> 입력 배열을 두 개의 부분 배열로 분할

    > 각 부분 배열의 원소가 하나가 될 때까지 반복

> 부분 배열을 병합

    > 이때 병합된 배열의 원소가 정해진 정렬 순서에 부합되도록 순서를 조정

 

- 병합 정렬의 시간 복잡도

> 배열을 분할 또는 병합하는 단계 : log n

> 배열 병합하는 과정의 시간 복잡도 : O(n)

> 전체 시간 복잡도 : O(n log n)

 

- 병합 정렬의 특징

> 실제 정렬이 이루어지는 시점은 두 개의 부분 배열이 병합하는 단계임

> 안정된 정렬이며 데이터의 초기 순서에 영향을 크게 받지 않음

> 병합 과정에서 임시 배열을 필요로 함 (공간 복잡도 : O(n))

 

- 병합 정렬 코드

#include <iostream>

using namespace std;

// int buff[256]; 로 전역변수로 할당함
int buff[256];

// 병합 함수
void merge(int data[], int left, int mid, int right)
{
    int i = left, j = mid + 1, k = left;
    // 한개씩 비교 하는 코드
    while (i <= mid && j <= right){
        if (data[i] <= data[j])
            buff[k++] = data[i++];
        else
            buff[k++] = data[j++];
    }
    
    while (i <= mid)
        buff[k++] = data[i++];
    while (j <= right)
        buff[k++] = data[j++];
    // 정렬된 데이터 복사하기
    for (int x = left; x <= right; x++)
        data[x] = buff[x];
}

void merge_sort(int data[], int left, int right)
{
    if (left < right) {
        int mid = (left + right) / 2;
        merge_sort(data, left, mid);
        merge_sort(data, mid + 1, right);
        // 병합
        merge(data, left, mid, right);
    }
}

int main()
{
    int data[] = {2, 6, 7, 4, 1, 8, 5, 3};
    merge_sort(data, 0, 7);
    
    for (auto n : data)
        cout << n << ", ";
    cout << endl;
}

 

 

- 퀵 정렬(quick sort)

> 병합 정렬과 마찬가지로 분할 정복에 의한 정렬 알고리즘

> 특정 원소를 피벗으로 선택하고, 주어진 배열을 피벗보다 작은 부분과 큰 부분으로 분할

    > 피벗 : 비교 기준 원소

> 분할된 부분 배열에 대해 재귀적으로 퀵 정렬 분할 작업을 반복

 

- 퀵 정렬의 시간 복잡도

> 최선의 경우 : O(n log n) (항상 절반으로 분할되는 경우)

> 최악의 경우 : O(n^2) (한 쪽은 1개, 다른 쪽은 n-1개로 분할되는 경우)

 

- 퀵 정령의 특징

> 실제 정렬이 이루어지는 시점은 배열을 피벗 기준으로 분할하는 단계임

> 안정되지 않은 정렬이며 데이터의 초기 순서의 영향을 크게 받음

> 평균적으로 가장 빠른 정렬 알고리즘 -> C/C++ 라이브러리로 기본 제공되는 정렬 알고리즘

 

#include <iostream>
#include <algorithm>

using namespace std;

int partition(int data[], int left, int right)
{
    int pivot = data[left];
    int i = left + 1, j = right;
    
    while (true){
        // i를 증가시키면서 pivot보다 큰 data[i] 선택
        while (data[i] <= pivot && i <= right)
            i++;
        // j를 감소시키면서 pivot보다 작은 data[i] 선택
        while (data[j] > pivot && j > left)
            j--;
        // 만약 i < j 이면 data[i]와 data[j]를 교환하고, 1) i를 증사키는 코드부터 다시 시작
        if (i < j)
            swap(data[i], data[j]);
        // 그렇지 않으면 pivot과 data[j]를 교환
        else
            break;
    }
    swap(data[left], data[j]);
    return j;
}

void quick_sort(int data[], int left, int right)
{
    if (left < right){
        // parition 함수는 피벗 기준으로 배열을 재배치하는 함수이다.
        int p = partition(data, left, right);
        quick_sort(data, left, p - 1);
        quick_sort(data, p + 1, right);
    }
}

int main()
{
    int data[] = {5, 6, 7,3, 1, 9, 2, 4,8};
    // data배열, 배열의 첫번째 인덱스에 해당하는 0을 입력으로 줌, data의 크기 9 - 1
    quick_sort(data, 0, size(data) - 1);
    
    for (auto n : data)
        cout << n << ", ";
    cout << endl;
}

- 힙 정렬(heap sort)