ALDS1_2_B 選択ソートをC++で解いてみた[AIZU ONLINE JUDGE]

こんにちは！ mnbd（@mnbbbbbd）です。

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

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

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

問題文

選択ソートは、各計算ステップで１つの最小値を「選択」していく、直観的なアルゴリズムです。

1 selectionSort(A, N) // N個の要素を含む0-オリジンの配列A
2 for i が 0 から N-1 まで
3 minj = i
4 for j が i から N-1 まで
5 if A[j] < A[minj]
6 minj = j
7 A[i] と A[minj] を交換

数列Aを読み込み、選択ソートのアルゴリズムで昇順に並び替え出力するプログラムを作成してください。上の疑似コードに従いアルゴリズムを実装してください。

疑似コード 7 行目で、i と minj が異なり実際に交換が行われた回数も出力してください。

入力
入力の最初の行に、数列の長さを表す整数 N が与えられます。２行目に、N 個の整数が空白区切りで与えられます。

出力
出力は 2 行からなります。１行目に整列された数列を 1 行に出力してください。数列の連続する要素は１つの空白で区切って出力してください。2 行目に交換回数を出力してください。

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/2/ALDS1_2_B

解答

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

void print_array(int a[], int n) {
    for(int i = 0; i < n; i++) {
        cout << a[i];
        if(i != n - 1) {
            cout << " ";
        } else {
            cout << endl;
        }
    }
}

int selection_sort(int a[], int n) {
    int count = 0;
    for(int i = 0; i <= n - 1; i++) {
        int min = i;
        for(int j = i; j <= n - 1; j++) {
            if(a[j] < a[min]) {
                min = j;
            }
        }
        if(a[i] != a[min]) {
            swap(a[i], a[min]);
            count++;
        }
    }
    return count;
}

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

    int count = selection_sort(a, n);
    print_array(a, n);
    cout << count << endl;

    return 0;
}

感想

選択ソートの問題ですが、問題文中にアルゴリズムが書いてあるので、それをc++に書き換えたものです。

値の交換数をカウントしますが、そのまましてしまうと合格できません。

問題文にある、実際に交換したかどうかを判定する必要がありました。

まとめ

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

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