バブルソートについて書きましょう。これは数値の組を大小順に並べ替える方法のひとつです。前回クイックソートの話をしました。クイックソートは「最速」ということになっています。
しかしバブルソートは遅いのです。バブルソートはデータ数n(大きな数)に対し、大体n*nの定数倍程度の手数がかかります。クイックソートはnが大きければ n*log n の定数倍程度だそうです。これはnが大きいときに圧倒的な差となって現れます。例えばn=100万のとき、n*n=1億2千万、n*log n = 600万です。
なお、計算量をちゃんと議論するにはランダウの記号「O」を用います。適当なMを定めれば、十分大きなnに対し|f(n)|<M|g(n)|であるときf(n) = O(g(n))と表す、というものです。これを使うと、クイックソートの計算量はO(n * log n)です。今回はランダウの記号についてはこれだけにしておきます。
さて、次のデータのセットをバブルソートしましょう。
[5,2,1,4,6,4,8,9,6,4]
まず先頭の2個の大小を比較します。5>2ですから、5,2を入れ替えます。
[2,5,1,4,6,4,8,9,6,4]
次に5,1を比較して入れ替えます。
[2,1,5,4,6,4,8,9,6,4]
次に5,4を比較して入れ替えます。
[2,1,4,5,6,4,8,9,6,4]
次に5,6を比較しますが、5<6なので入れ替えません。次に6,4を比較して入れ替えます。
[2,1,4,5,4,6,8,9,6,4]
これを最後のデータまで繰り返すと
[2,1,4,5,4,6,8,6,4,9]
となります。
ここまでで9回の比較、交換をしました。先頭に戻り、また9回の比較、交換をします。また先頭に戻り、9回の比較、交換を……と繰り返します。これを9周、繰り返すのです(従って比較、交換は81回)。なぜ9周か。データの一番右に最も小さいデータがあったとすると、これはソート後、一番左に来なければなりません。上の操作は1周(データを左端から順に比較して右端まで)だと1データ分左に動くだけですから、合計9周ループしなければならないのです。
ブクブク泡立つようにデータが動きますからバブルソートです。泡立ち法とも言います。
本当に面白いのは今回少し書いたような計算量の話かも知れません。計算可能性、計算量の理論、この辺をやってみたい……。学校はまもなく冬休み、受験生は大変ですが(特に今回はコロナ、新しい大学入試共通テストで)そうでなければ勉強のチャンスです。
コロナは先が見えませんね。5月頃は憂鬱だったけれど、慣れたのか今ではもちろんイヤではありますが憂鬱というほどでもありません。しかし特に新しい学校に入学して最初の学年の学生たちはかわいそうな気がします。せっかく一番楽しい時期なのに……。