マージソートを理解する

前回に引き続き今回はマージソートについてです

マージソートって？

クイックソートと同じく処理が速いものとなりますが、ソート時に複数の配列を作成する必要があるため、メモリを消費するという難点があります。詳しくは以下のサイトがわかりやすいと思います

マージソートを実装する

ランダム配列は前回の記事で作成したものを使用します。それでは実際にマージソートをC＋＋で実装してみます

template <typename T>
void mergeSort(std::vector<T>& arr, int left, int right) {
    if (left < right) {
        int middle = left + (right - left) / 2;

        // 左半分をマージソート
        mergeSort(arr, left, middle);

        // 右半分をマージソート
        mergeSort(arr, middle + 1, right);

        // マージ
        merge(arr, left, middle, right);
    }
}

まずは再帰的に呼び出す関数を用意します。配列の入れ替えを実施する関数は別で用意します

template <typename T>
void merge(std::vector<T>& arr, int left, int middle, int right) {
    int n1 = middle - left + 1;
    int n2 = right - middle;

    // 一時的なベクターを作成
    std::vector<T> leftArray(n1);
    std::vector<T> rightArray(n2);

    // 左半分を一時的なベクターにコピー
    for (int i = 0; i < n1; i++) {
        leftArray[i] = arr[left + i];
    }

    // 右半分を一時的なベクターにコピー
    for (int j = 0; j < n2; j++) {
        rightArray[j] = arr[middle + 1 + j];
    }

    // マージ
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (leftArray[i] <= rightArray[j]) {
            arr[k] = leftArray[i];
            i++;
        } else {
            arr[k] = rightArray[j];
            j++;
        }
        k++;
    }

    // 左半分に残った要素をコピー
    while (i < n1) {
        arr[k] = leftArray[i];
        i++;
        k++;
    }

    // 右半分に残った要素をコピー
    while (j < n2) {
        arr[k] = rightArray[j];
        j++;
        k++;
    }
}

最期に配列の中身を入れ替える関数を実装します

実際に動かしてみる

検証用の配列を作成し、それをマージソートで並び替えて結果を見てみましょう

std::vector<int> arr = RandomCreate();
int size = arr.size();

std::cout << "Original Array: ";
for (int i : arr) {
    std::cout << i << " ";
}
std::cout << std::endl;

mergeSort(arr, 0, size - 1);

std::cout << "Sorted Array: ";
for (int i : arr) {
    std::cout << i << " ";
}
std::cout << std::endl;

マージソートを用いて配列が並び変えられていることが確認できました