정렬2 : 분할정복을 이용한 정렬

분할정복을 이용한 정렬

• Merge Sort
• Quick Sort

 

 

Merge Sort

merge sort

• pseudo algorithm

1. 정렬할 데이터 집합을 반으로 나눈다

2. 나누어진 하위 데이터 집합의 크기가 2이상이면 이 하위 데이터 집합에 대해 1번 작업을 반복한다

3. 원래 같은 집합에서 나뉘어진 두 개의 하위 데이터 집합의 원소들을 크기 순서에 맞춰 정렬하고 병합.

4. 데이터 집합이 하나가 될 때까지 3번작업을 반복

 

• 시간복잡도
  • worst : O(nlogn)
  • average : O(nlogn)
  • best : O(nlogn)

 

 

• 예시 코드

// merge sort

#include <iostream>
#include <vector>
#define MAX_SIZE 9
using namespace std;

vector<int> arr(MAX_SIZE);
vector<int> sortedArr(MAX_SIZE);
void mergeSort(vector<int>& arr, int left, int right);
void merge(vector<int>& arr, int left, int mid, int right);

int main() {

    for (int i = 0; i < arr.size(); i++) 
        arr[i] = (601 * (i + 3)) % 271;
    cout << "before sorting : ";
    for (int i = 0; i < arr.size(); i++)
        cout << arr[i] << " ";

    mergeSort(arr, 0, (MAX_SIZE-1));

    cout << endl << "after sorting : ";
    for (int i = 0; i < arr.size(); i++)
        cout << arr[i] << " ";

    return 0;
}

//divide
void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) { // 원소 최소 2개 이상
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid+1, right);
        merge(arr, left, mid, right);
    }
}

//conquer
void merge(vector<int>& arr, int left, int mid, int right) {
    int i = left;
    int j = mid + 1;
    int k = left;

    // 정렬
    while (i<=mid && j<=right){
        if (arr[i] < arr[j])
            sortedArr[k++] = arr[i++];
        else
            sortedArr[k++] = arr[j++];
    }

    // 남은 부분 복사 : 왼쪽이 남은경우
    while (i <= mid) {
        sortedArr[k++] = arr[i++];
    }

    // 남은 부분 복사 : 오른쪽이 남은 경우
    while (j <= right) {
        sortedArr[k++] = arr[j++];
    }

    // 정렬된 결과를 원래 배열로 복사
    for (int l = left; l <= right; l++) {
        arr[l] = sortedArr[l];
    }
}

 

 

 

Quick Sort

quick sort

 

• 분할 정복 알고리즘을 이용한 매우 빠른 수행 속도를 자랑하는 정렬
• 합병 정렬(merge sort)과 달리 퀵 정렬은 리스트를 비균등하게 분할한다.
• psuedocode

1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.
2. 피벗을 기준으로 피벗보다 작은 요소들은 피벗의 왼쪽, 피벗보다 큰 요소들은 피벗의 오른쪽으로 나눈다 
3.  피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
   • 분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복한다.
   • 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
4. 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다. 리스트의 크기가 0이나 1이 될 때까지 반복한다.

• 시간복잡도
  • worst : O(n^2)
  • average : O(nlogn)
  • best : O(nlogn)
• 예시코드

// quick sort

#include <iostream>
#include <vector>
#define MAX_SIZE 9
using namespace std;

vector<int> arr(MAX_SIZE);
void quickSort(vector<int>& arr, int start, int end);
int partition(vector<int>& arr, int start, int end);

int main() {

    for (int i = 0; i < arr.size(); i++)
        arr[i] = (601 * (i + 3)) % 271;
    cout << "before sorting : ";
    for (int i = 0; i < arr.size(); i++)
        cout << arr[i] << " ";  // 177 236 24 83 142 201 260 48 107

    quickSort(arr, 0, (MAX_SIZE - 1));

    cout << endl << "after sorting : ";
    for (int i = 0; i < arr.size(); i++)
        cout << arr[i] << " ";  // 24 48 83 107 142 177 201 236 260 

    return 0;
}

void quickSort(vector<int>& arr, int start, int end) {
    if (start < end) {
        int idx = partition(arr, start, end);
        quickSort(arr, start, idx - 1);
        quickSort(arr, idx + 1, end);
    }
    else
        return;
}

int partition(vector<int>& arr, int start, int end) {
    int pivot = arr[end];   // 정렬의 기준 : 정렬할 구간의 맨 오른쪽 원소 선택
    int idx=start;          // 피봇값을 정렬할 구간을 둘로 나누는 위치값
    int temp;              

    for (int i = start; i < end; i++) {
        if (arr[i] <= pivot) {
            temp = arr[i];
            arr[i] = arr[idx];
            arr[idx] = temp;
            idx++;
        }
    }

    temp = arr[idx];
    arr[idx] = arr[end];   
    arr[end] = temp;
    
    // idx 기준으로 idx 보다 작은 인덱스는 모두 arr[idx]값 보다 작은원소들
    // idx 보다 큰 인덱스는 모두 arr[idx] 값 보다 크다.
    return idx; 
}