flagを用いたバブルソート

Question

前提・実現したいこと

flagを用いたバブルソートの流れを理解したいです。

１．関数bubbleSort()の中は、まず「bool flag = 1;」で、「for (int i = 0; flag; i++)」の「flag」は「1」になり、

２．次に「for (int j = N - 1; j >= i + 1; j--)」で「j >= i + 1;」の「i」は「0」、「1」が順番に入り、

３．「if (A[j] < A[j - 1])」でAの配列を後ろから比較して、後ろの数「A[j]」より、前の数「A[j - 1]」が小さければ、「swap(A[j], A[j - 1]」して、flag = 1になので、

４．「for (int i = 0; flag; i++)」の「flag」が「1」になるので、また内側のループに入り、比較を行う。

５．１．～４．を最大でもN回繰り返し、ソート終了。

この１．～５．の流れで理解はあっていますでしょうか？
自分の中ではflagはオン・オフとはネットで調べたのですが、いまいち流れが分かりません。
よろしくお願い致します。

発生している問題・エラーメッセージ

エラーメッセージ

該当のソースコード

#include<iostream>
using namespace std;

int bubbleSort(int A[], int N) {
    int sw = 0;
    bool flag = true;
    for (int i = 0; flag; i++) {
        flag = false;
        for (int j = N - 1; j >= i + 1; j--) {
            if(A[j] < A[j - 1]) {
                swap(A[j], A[j - 1]);
                flag = true;
                sw++;
            }
        }
    }
    return sw;
}

int main() {
    int A[100], N, sw;
    cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i];
    
    sw = bubbleSort(A, N);
    
    for (int i = 0; i < N; i++) {
        if (i) cout << " ";
        cout << A[i];
    }
    cout << endl;
    cout << sw << endl;
    
    return 0;
}

試したこと

ここに問題に対して試したことを記載してください。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Comments

[cateye]

そもそも、bool値に１とか０とかって？

[whitehorse85921]

cateyeさん、ありがとうございます。
私もこのコードが掲載されているアルゴリズムとデータ構造の本を読み始めたばかりなので、なぜ、bool値に1とか0が代入されているのか分かりません。
すみません。

[cateye]

元がCのソースならしょうがないですが、ｃ＋＋なら１をtrueに０をfalseに読み替えましょう。
私の持っている「アルゴリズムとデータ構造」はPascalなんで・・・違いますね・・・orz

[whitehorse85921]

cateyeさん、ありがとうございます。
はい、さっそく書き換えます。

Answer 1

flagって名前が宜しくないんだと思う。

こいつは要するに内側のloopで少なくとも一回は交換を行ったことを意味する。

一度も交換が行われなかったら(flagがfalseなら)交換の必要がなかった、つまりソート完了ってこと。
裏返せば、一度でも交換が行われたら(flagがtrueなら)、再度内側のloopを回す必要があるってこと。

※ なので僕なら bool swapped と命名する。

Comments

[whitehorse85921]

epistemeさん、ありがとうございます。
その「一度でも交換」とは、具体的にどういうことでしょうか？
「一度」とは、外側のループが1週目の時に内側のループに1回でも交換があったときでしょうか？
例えば、配列A[1,5,3,2,4]があったとして、後ろの要素2,4は交換が必要なくても、次の要素の比較3,2は交換が必要になるので、これを「一度でも交換」と仰ったと理解してもよろしいでしょうか？

何度もすみません。
よろしくお願いいたします。

[episteme]

内側のloopで交換したらflagを1にしてるっしょ？

[whitehorse85921]

epistemeさん、ありがとうございます。
「内側のループで交換したらflagを1にする」のは分かります。
ただ、if(A[j] < A[j - 1]）の比較の時点で、上記の配列A[1,5,3,2,4]を後ろから比較していったときに、2,4は交換する必要がないように思われるのです。
理解が遅くすみません。

[episteme]

それで？
「内側のloopで一度も交換しなかったらソート完了」に納得できませんか？

[whitehorse85921]

epistemeさん、ありがとうございます。
なんとなく納得いたしました。