基礎プログラミング II 第 5 回 (何度も呼び出そう) 「とりあえず全部並べる」 講義ノート目次

順序が決まっているものを並べかえる作業は、どう行っているのだろうか。 例えば左から順に 1 からはじめて、5 までを並べかえることにする。 よく切ったあと、全て並べてみる。左端のカードを選ぶ。

(*) 左から順に、右隣とくらべて、大きければ入れ替える。 左隣が自分より小さく、右隣が自分より大きくなるまで実行する。

終了したらまた左端のカードを選ぶ。(*) くりかえし。

左端の 4 を右隣の 5 とくらべる。この場合は順番どおり。

45321

5 を選ぶ。右隣の 3 は小さいので、入れ替える。

43521

5 を選ぶ。右隣の 2 は小さいので、入れ替える。

43251

次に 5 を選ぶ。右隣の 1 は小さいので、入れ替える。

43215

右隣はなくなったので、また左端へ戻る。左端の 4 について、右隣の 3 は 小さいので入れ替える。

34251

以下くりかえす。

トランプのカードでなくてもよい。不要な紙を 8 等分にして、 この試行を再現せよ。

並べかえが完成すると、全ての数字が並ぶ。

12345

このような並べかえを bubble sort と呼ぶ。ソースはこれ。