バブルソート

質問

int a[] = {8,45,15,90,62,73,22}をバブルソートを使用して、降順で並べ替える。
以下の説明では、配列の要素数（ここでは７）をＮとしている。

(1) a[N-1] と a[N-2] を比較し、a[N-1] が a[N-2] より大きい場合は、a[N-1] と a[N-2] を入れ替える。
　　同様に a[ j] が a[ j-1] より大きければ、a[ j] と a[ j-1] を入れ替える。
　　この操作を、j=N-1からiまで繰り返す。ただし、iは(1)の処理回数を表す値である。(初回を0とする）

(2) (1)を i=0 から N-2 まで繰り返す。

(3) 以下の<実行例>を参考に、配列ａのようその各値を標準出力する。

<実行例>
90 73 62 45 22 15 8

という問題なのですが、どうやってもうまく並び替えられません。
a[N-1] の処理はいらないのではないのですか？
どのようにプログラムを書いたらいいのか教えて下さい。
あつかましいですが、できたら解説付きでお願いします。

回答No.2

ymmasayan · ベストアンサー

問題文がごちゃごちゃしすぎていますね。

まず、バブルソートは正式（？）には隣接交換法といいます。隣同士を順番に交換していきます。
一番泥臭く考えれば、右端から左端へ何回移動すれば整列が完了するでしょうか。
最も悪条件は左端に一番小さいデータがあって、これを右端へ移動させると考えると（Ｎ－１）回であることはすぐわかりますね。つまり、隣同士を比較しながらの右から左への移動（比較回数はＮ－１回）が（Ｎ－１）回で整列が完了する事になります。

ところが、これには無駄があります。右から左へ動いていくとき、必ず一番大きいデータが左端へ移動していきます。１回目は１番大きいデータ、２回目は２番目に大きいデータという風にです。従って、一番左に行ったデータは次からは比較の対象からはずしていいのです。（余談ですが大きい泡ほど早く水面に達するという現象になぞらえて、泡ソート＝バブルソートというあだ名がついています。）

従ってｆｏｒ文の２重ループが次の様になる事はお判りですね。

ｆｏｒ(　)…比較の対象範囲の左端を管理するループ（ｉ＝０～Ｎ－２）
　　　　　　（最低でも２個ないと比較できないので、Ｎ－１でなく，Ｎ－２）
　　ｆｏｒ(　)…１回ごとの比較の左端を管理するループ（ｊ＝（Ｎ－２）～ｉ）
　　　　　　　（これはｊ－－　である事に注意が必要です）

＞a[N-1] の処理はいらないのではないのですか？

いります。問題の書き方がよくないだけです。
a[N-1] と a[N-2] の比較からはじめて 一般形としてa[ j] と a[ j-1] の比較をする。逆転があれば入れ替える。という風に読まないといけないのです。
わかりにくい問題文で苦労させられているご様子、同情します。

お礼

すみません、お礼が遅れました。
細かく、そしてわかりやすく説明してくださってありがとうございました。
読めば読むほどややこしくて…。
なんとか成功しました。

回答No.3

imogasi

下記はＶＢＡでやって見ました。ご参考になれば。
何となく、質問の例の配列の要素（添え字）は理解し難い。
（Ｂ）のところは１回左より右へ比較が終わると、最小
が右のほうのＪ＋１番目に決まるので
第１回目　　０から５まで
第２回目　　０から４まで
・・・・
と１つずつ減っていく。
それで（Ａ）のところで５から１づつ減る変数ｊを５から
０まで１づつ減らしている。
Sub test01()
a = Array(8, 45, 75, 90, 62, 73, 22)
For j = 5 To 0 Step -1 '-----(A)
For i = 0 To j '-------------(B)
If a(i) > a(i + 1) Then
Else
W = a(i)
a(i) = a(i + 1)
a(i + 1) = W
End If
Next i
Next j
'------
For i = 0 To 6
Debug.Print a(i)
Next i
End Sub

お礼

お礼が遅れましてすみません。
わざわざのご回答ありがとうございました。
かかれてあることをちょっとずつ噛み締めて、なんとか成功することが出来ました。

回答No.1

taka_tetsu

これぐらいの個数でしたら、並びの変化を目で見ながら追っていくと理解しやすいですよ。

初期値
8,45,15,90,62,73,22
1回目
90,8,45,15,73,62,22
2回目
90,73,8,45,15,62,22
3回目
90,73,62,8,45,15,22
4回目
90,73,62,45,8,22,15
5回目
90,73,62,45,22,8,15
6回目
90,73,62,45,22,15,8

というように、最高6回のループでソートが完了します。
つまり、N-1回です。

(2)のN-2と書くとわかりづらいかもしれませんね。

for文で書くと、

for(i = 0; i < N-1; i++ )

こんな感じになります。

あと、バブルソートは、1回ループが終了するごとに先頭の値が決定するので比較の回数が1回ずつ少なくなっていくのがポイントです。

例：
2回目のループのとき、1回目で先頭にきた90と73の比較を行う必要はない。

こんな感じですかね。
バブルソートくらいですと、ソースを書くと答えになってしまうので・・・

そのまま書くと勉強にならないですし。

お礼

お礼が大変送れて申し訳ありません。
一から動きを確認し、少しずつ動かしていったらなんとか出来ました。
本当に初心者でお恥ずかしい。
ありがとうございました。