クイックソート

クイックソート(Quick Sort)は典型的な分割征服アルゴリズムであり,平均速度はO(N x logN)であった.O(n^2)の選択、挿入、Bubbleソートと比較して、高速ソートアルゴリズムです.しかし,ある程度並べ替えが行われており,分割征服特性を利用できない特定の場合には,O(N^2)の時間的複雑さがある可能性がある.

平均時間複雑度:O(N x logN)

最悪時間複雑度:O(N^2)

なぜ分割征服アルゴリズムが速いのですか?
例えば,O(N^2)の時間的複雑さがあると仮定する.
[1,2,3,4,5,6,7,8,9,10]のカウントは10 x 10=100であった.
半分を分割して征服すれば
[1,2,3,4,5]の場合、5 x 5=25
[6,7,8,9,10]の場合、5 x 5=25
25+25=50で、合計50回実行され、回数が減少します.

ステージ

まず簡単にまとめると,クイックソートは特定の基準値(Pivot)を基準として,大きな値と小さい値を互いに交換し,配列を半分に分ける方式である.以下の例で説明します.

の最初の値(8)をpivot値として指定します.

pivot値と比較して、左から右に大きな値を検索し、右から左に小さな値を検索します.このとき、大きい値(10)のインデックスは小さい値(2)のインデックスよりも小さいため、2つの値が互いに交換される.

を再検索します.このとき、大きい値(10)のインデックスは小さい値(3)のインデックスよりも大きいため、小さい値3とpivot値とが入れ替わる.

で交換されたpivot値(8)はソートを完了し、8に基づく左右のセットに対して上記の手順を繰り返す.(分割征服)

8を基準として、左グループの最初の値(3)をピボット値として指定して検索します.

大きい値(5)のインデックスは小さい値(1)のインデックスより小さいため、2つの値が互いに交換される.

を再検索すると、大きな値(5)のインデックスは小さな値(1)のインデックスよりも大きいため、小さな値とpivot値が互いに交換される.

で交換されたpivot値(3)はソートが完了し、3に基づいて再分割された左右のセットに対して上記の手順を繰り返す.(分割征服)

3を基準として、左グループの最初の値(1)をpivot値として指定して検索します.このとき,大きな値(2)が見つかったが,小さな値が見つからなかったためpivot値(1)に達した.また、大きい値(2)のインデックスが小さい値(1)のインデックスよりも大きいため、小さい値(1)とpivot値(1)を交換する.お互いに自分を交換するので、変わっていません.

で交換されたpivot値(1)はソートを完了し、1ベースの左右セットについては上記の手順を繰り返す必要があるが、左側はないため、右側に対して実行をスキップする.-(分割征服)

このような手順を繰り返すと、ソートが完了します.この過程でよく考えてみると,パーティション征服がうまくいかなければ,性能が悪い原因も分かる.

インプリメンテーション

#include <stdio.h>

int number = 10;
int arr[] = {1, 3, 6, 9, 10, 4, 7, 8, 2, 5};

void quickSort(int *arr, int start, int end) {
    if (start >= end) return;

    int key = start;    // 기준값(Pivot)
    int i = start + 1;
    int j = end;
    int temp;

    // 엇갈릴 때까지 반복
    while (i <= j) {
        // key보다 큰 값을 만날 때까지 
        while (arr[key] >= arr[i] && i <= end) {
            i++;
        }
        // key보다 작은 값을 만날 때까지 
        while (arr[key] <= arr[j] && j > start) {
            j--;
        }

        // 엇갈리면 작은 값과 key값 swap 
        if (i > j) {
            temp = arr[key];
            arr[key] = arr[j];
            arr[j] = temp;
        // 엇갈리지 않으면 i,j값 swap 
        } else {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // key값 기준으로 양쪽을 재귀로 분할 정복
    quickSort(arr, start, j-1);
    quickSort(arr, j+1, end);
}

int main() {
    quickSort(arr, 0, number-1);
    for (int i=0; i<number; ++i) {
        printf("%d ", arr[i]);
    }
    return 0;
}

連結ソート

マージソート(Merge Sort)は、高速ソートと同様に、O(N x logN)の時間的複雑さを有する典型的な分割征服アルゴリズムでもある.しかし、特定の場合にO(N^2)という最悪時間の複雑さを持つ高速ソートとは異なり、マージソートはより多くのメモリを使用しているが、最悪の場合でもO(N x logN)を保証できることが最大の特徴である.

ステージ

連結ソートの概念は、1つずつ分離するまで、すべて2つに分割し、連結時にソートを実行することです.

なぜ

の高さはlogNですか?

は無条件に半分になっているので、フェーズの数はlog(data의 개수)-(ほぼ定数に等しい)

幅はなぜNですか?

が結合した集合間で比較演算を行うのは,なぜNだけがおかしいのか.これは、マージ後の古いコレクションが別々にソートされているためです.

インプリメンテーション

#include <stdio.h>

int sorted[10];

void merge(int arr[], int m, int mid, int n) {
    int i = m;          // 앞 배열의 idx
    int j = mid + 1;    // 뒷 배열의 idx
    int k = m;          // sorted[]의 idx

    // 작은 순서대로 sorted[]에 삽입, idx 증가
    while (i <= mid && j <= n) {
        if (arr[i] <= arr[j]) {
            sorted[k] = arr[i];
            i++;
        } else {
            sorted[k] = arr[j];
            j++;
        }
        k++;
    }

    // 앞, 뒷 배열의 삽입이 먼저 완료될 때 나머지 데이터 삽입
    if (i > mid) {
        for (int t=j; t<=n; t++) {
            sorted[k] = arr[t];
            k++;
        }
    } else {
        for (int t=i; t<=mid; t++) {
            sorted[k] = arr[t];
            k++;
        }
    }

    // 임시로 sorted[]에 저장된 배열을 삽입 
    for (int t=m; t<=n; t++) {
        arr[t] = sorted[t];
    }
}

void mergeSort(int arr[], int m, int n) {
    // 분할 정복(재귀)
    if (m < n) {
        int mid = (m + n) / 2;
        mergeSort(arr, m, mid);
        mergeSort(arr, mid+1, n);
        merge(arr, m, mid, n);
    }
}

int main() {
    int arr[10] = {7, 6, 5, 8, 3, 5, 9, 1, 2, 10};
    mergeSort(arr, 0, 9);
    for (int i=0; i<10; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}