バブルソートの比較回数

Question

前提・実現したいこと

配列を昇順に並び替えたいので、バブルソートのコードをインターネットで
参考にしてプログラムに組み込んだのですが、いまいち比較回数の array.length - 1 - i
の意味が分かりません。
if以下の並び替えの意味は分かるのですが、どうしてもそこが引っかかって理解が進みません。
どうか解説をよろしくお願い致します。

該当のソースコード

for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;

Answer 1

こんなかんじ 引用

Comments

[pepperleaf]

見事なイメージ図。解説があるともっと良いですが。

Answer 2

わからなくなったら、具体的な数値で考えましょう。
例えばarray.lengthが10だとしましょう。配列のインデックスは

[0][1][2][3][4][5][6][7][8][9]

のようになります。
まずi=0の状態を考えます。j=0から始まるため、[0]と[1]の比較から始まり、[1]と[2],[2]と[3],...のように順次比較および交換が起こります。
最後の比較は[8]と[9]の比較となり、この時のjは8です。つまり、jは9未満の範囲で回すことになります。ここで[9]に入っているものがこの中で最大で確定します。

[0][1][2][3][4][5][6][7][8] | [9]
                               ↑確定

次にi=1の状態を考えます。[9]は確定していて動かす必要がないため、[7]と[8]まで比較すれば十分ということになります。このラストのjは7となるため、jは8未満で回すことになります。

ここまでで法則性が見えてきませんか？

Comments

[tukikai-incid]

法則性を見つけられました！
ありがとうございましたm(__)m

Answer 3

バブルソートは本質的に以下の手順を行っています。

- 集合が空になるまで
    - 集合の中から一番大きな要素を探し、
    - その要素を集合から除去する

この各手順がトリッキーで面白く、

集合の中から一番大きな要素を探し、

隣り合う2つの要素を比較して大きな方を右側に持ってくる、という操作を検査範囲の左から右にかけてズラッと行うことで、一番大きな要素が一番右側にきます。

その要素を集合から除去する

検査範囲を1つ狭め、一番右側の要素（さっき探した一番大きな要素）を検査範囲から外します。

最終的に検査範囲が空になった時点で自動的に整列済み配列が残るっていう仕組みです。

for (int j = 0; j < array.length - 1 - i; j++)
↑このfor文が見る範囲が現在の検査範囲であり、iが1増えるたびに検査範囲が1狭まっていきます。

Comments

[tukikai-incid]

検査範囲を1つ狭め、一番右側の要素（さっき探した一番大きな要素）を検査範囲から外します。

が分かっていませんでした。
一番分かりやすい説明でしたのでBAに選びました。
ありがとうございます！

Answer 4

まず、 -1 の意味は、if 文で、 j+1 を見ているので、一つ手前で良いですね。
-i の意味は、最初のループで、最大値が確定しているので、その手前まで、調べれば、良いという意味ですね。比較しても良いでしょうが、不要な処理という事になります。

この辺は、最初から、大きい数で行うと分かりにくいので、 少ない数(5 とか、6とか)で、for ループを追いかけるのも一つの手かも知れません。