のんちゃんのVBお勉強に協力する試み (1) のつづき。
さてさて、ヒントめいたのを書きつけておきましょか。
まず、「昇順(小さい順)にソートされた状態」とはなにか。
data(n) (n=0..N-1) において0以上N未満であるいかなるi,j に
対しても、i < j ならば data(i) <= data(j) が成り立つ
ってこと。
もっといえば隣り合うふたつのデータについて
data(i) <= data(i+1) が成り立つってことです。
ってことは、data(i)とdata(i+1)を比較し、
data(i) > data(i+1) となってる箇所があれば
その二つを交換すればいい。
この比較と交換をくまなく行って逆順すなわち
data(i) > data(i+1) がひとつも見つからなくなればソート完了。
「比較と交換をくまなく行う」これがバブルソートのキモです。
それじゃくまなく行うにはどうすりゃいいか、
左端(i=0)からひとつずつ順にやってきゃいいわな。
たとえば 1 3 2 1 から始めて左端から一回通してみよう。
( . の左右が比較してるとこ)
1.3 2 1
1 3.2 1 → 1 2 3 1 (ここで交換)
1 2 3.1 → 1 2 1 3 (ここで交換)
こうやって一回通すと一番大きな要素が右端に寄ってくれる。
けどもまだ完全にはソートされてない。なのでもう一回。
右端が最大になってるんだから最後の比較/交換の必要はない。
1.2 1 3
1 2.1 3 → 1 1 2 3
1 1 2 3 完了!
つまり、一回でも交換を行うとそれによって大小が狂うかも
しれんのでさらにもう一回左から比較/交換を行う。
一度も交換が行われなかったらそれがソート完了の証しとなるんやね。
負けるもんかが「ﾄﾃｰﾓ大きなヒントになってんだよ」てのは
くまなく行うを実現してるとこね。