C/C++アルゴリズム

C・C++のマージソート（merge sort）

このレッスンでは、常にO(n log n)の時間で動く、分割統治のマージソートを実装します。

はじめに

マージソートは配列を2つに分け、それぞれを再帰呼び出しで並べ替えてから、並んだ2つを1つの順序付きの並びに統合します。入力データがどんな状態でも、実行時間が常にO(n log n)で安定しているのが大きな利点です。

大切なポイント

空のデータ、要素が1つのデータ、重複を含むデータ、並べ替え済みのデータで試しましょう。
まず正しく動かし、最適化はその後にしましょう。
実際のコードでは、標準ライブラリの既製の関数を優先しましょう。

C・C++のマージソート（merge sort）のビジュアライザー

O(n)

再生またはステップを使って、比較とデータ移動を順に確認できます。

CとC++のコード例

実行 →

main.c

#include <stdio.h>
#include <stdlib.h>

void merge_sort(int *values, int *temporary, int left, int right) {
    if (right - left < 2) return;
    int middle = (left + right) / 2;
    merge_sort(values, temporary, left, middle);
    merge_sort(values, temporary, middle, right);

    int first = left;
    int second = middle;
    int output = left;
    while (first < middle && second < right) {
        temporary[output++] = values[first] < values[second]
            ? values[first++] : values[second++];
    }
    while (first < middle) temporary[output++] = values[first++];
    while (second < right) temporary[output++] = values[second++];
    for (int index = left; index < right; ++index) {
        values[index] = temporary[index];
    }
}

int main(void) {
    int values[] = {8, 3, 6, 2, 7};
    int temporary[5];
    merge_sort(values, temporary, 0, 5);
    for (int index = 0; index < 5; ++index) {
        printf("%d ", values[index]);
    }
}

実行結果

2 3 6 7 8

C++

実行 →

main.cpp

#include <algorithm>
#include <iostream>
#include <vector>

void merge_sort(std::vector<int>& values) {
    if (values.size() < 2) return;
    auto middle = values.begin() + values.size() / 2;
    std::vector<int> left(values.begin(), middle);
    std::vector<int> right(middle, values.end());
    merge_sort(left);
    merge_sort(right);
    std::merge(left.begin(), left.end(), right.begin(), right.end(),
               values.begin());
}

int main() {
    std::vector values{8, 3, 6, 2, 7};
    merge_sort(values);
    for (int value : values) {
        std::cout << value << ' ';
    }
}

実行結果

2 3 6 7 8

CとC++の比較

Cの関数merge_sortは、区間の要素が2個未満になると止まります。2つの半分を並べ替えた後、whileループが各半分の先頭のうち小さいほうを選んで一時配列temporaryにコピーし、残りもコピーします。どちらのバージョンもO(n)の追加メモリが必要です。Cは一時配列を自分で管理し、C++はvectorと標準アルゴリズムでコードをわかりやすくしています。

ループ、ポインタ、長さ、一時的なバッファをすべて明示的に書きます。

C++

イテレーターと標準アルゴリズムが、処理とデータの保存方法を切り離します。

発展問題

両方のバージョンを実行し、コードを書き換えて、それぞれの言語がもたらす安全性の違いを観察しましょう。

比較を1回ずつ紙の上でたどってみましょう。
重複した値や、とても大きい値・小さい値で試しましょう。
自分で書いたコードの実行時間を測り、標準ライブラリと比べましょう。

チャレンジで練習する

このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。

Count Inversions Count the out-of-order pairs in a list. 難しい

すべてのチャレンジ