ALDS1_5_B マージソートをC++で解いてみた[AIZU ONLINE JUDGE]

AIZU ONLINE JUDGE

こんにちは! mnbd(@mnbbbbbd)です。

プログラミング初心者なので、もっといい回答があるに違いありません。

あくまでも「動作はする」サンプルとしてご覧ください。

問題文

マージソート(Merge Sort)は分割統治法に基づく高速なアルゴリズムで、次のように実装することができます。

(マージソートのアルゴリズムについては以下のリンクに書かれています)

n 個の整数を含む数列 S を上の疑似コードに従ったマージソートで昇順に整列するプログラムを作成してください。また、mergeにおける比較回数の総数を報告してください。

入力
1行目に n、2行目に S を表す n 個の整数が与えられます。

出力
1行目に整列済みの数列 S を出力してください。数列の隣り合う要素は1つの空白で区切ってください。2行目に比較回数を出力してください。

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/5/ALDS1_5_B

解答

#include <bits/stdc++.h>
using namespace std;

int ans = 0;

void merge(int A[], int left, int mid, int right);

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

void merge(int A[], int left, int mid, int right) {
    int n1 = mid - left, n2 = right - mid;
    int L[n1], R[n2];

    for(int i = 0; i < n1; i++) {
        L[i] = A[left + i];
    }
    for(int i = 0; i < n2; i++) {
        R[i] = A[mid + i];
    }
    L[n1] = INT_MAX;
    R[n2] = INT_MAX;

    for(int i = 0, j = 0, k = left; k < right; k++) {
        if(L[i] <= R[j]) {
            A[k] = L[i++];
            ans++;
        } else {
            A[k] = R[j++];
            ans++;
        }
    }
}

int main() {
    int n;
	cin >> n;
    int S[n];
	for (int i = 0; i < n; i++) {
		cin >> S[i];
	}

    merge_sort(S, 0, n);

    for(int i = 0; i < n - 1; i++) {
        cout << S[i] << " ";
    }
    cout << S[n - 1] << endl;
    cout << ans << endl;

    return 0;
}

感想

マージソートの実装の問題ですが、マージソートの流れは問題文にあるので、それを言語に落とし込み問題と言えます。

まず、上の問題文にあるマージソートのアルゴリズムが間違えているので、それをそのまま実装してもうまく動作しません。

一般解説を読んで、マージソートを理解できれば、どこを修正すればいいのかわかります。

後は配列の添字を間違えてしまうことですね。

問題文の擬似コードと、言語特有の配列の書き方は違っていたりするので、そこもちゃんと理解する必要がありました。

まとめ

AIZU ONLINE JUDGEの「ALDS1_5_B マージソート」を解いてみましたので、その回答と解説をご紹介いたしました。

少しずつですが、プログラミングの勉強をしています。
まだ初心者ですが、よかったらつながっていただけると嬉しいです。
Twitterアカウント(@mnbbbbbd

以上です。
読んでいただきありがとうございました!