あるデータの集合を、50音順やアルファベット順、数値の大小などの一定の規則に従って並べ替えることを「ソート」といいます。
プログラミングでは、配列やコレクションの要素に対してソートを行う場面があります。

ソートには、いくつかのアルゴリズムがあり、その中のひとつが「バブルソート」です。
今回は、その「バブルソート」というのはどういうものなのかを解説し、Scratchで実装してみたいと思います。

バブルソートの手順

例えば、数値データが1つずつ入った箱が10個、縦に並んでいるとします。

現在、これらの箱の中の数値は順番がバラバラなので、これを上から数が小さい順（昇順）に並べ替えるとします。

これをバブルソートの手順で行うと、、

1) 一番下（10番目）の箱に入った数値と、そのひとつ上（9番目）の箱に入った数値を比較して、下側（10番目）の方が小さければ入れ替える。

2) 下から2番目（9番目）の箱に入った数値と、そのひとつ上（8番目）の箱に入った数値を比較して、下側（9番目）の方が小さければ入れ替える。

3) この比較を一番上の箱に辿りつくまで（2番目の箱と1番目の箱の比較）繰り返す。

ここまでの結果、10個の箱の中で一番小さい数の箱が、一番上になりました。
これで、一番小さい数は『確定』です。

次に、残りの9個の箱（10番目から2番目の箱）の中で一番小さい数（つまり全体では2番目に小さい数）の箱を、上から2番目に持ってくる作業を行います。

4) 一番下（10番目）の箱に入った数値と、そのひとつ上（9番目）の箱に入った数値を比較して、下側（10番目）の方が小さければ入れ替える。

5) 下から2番目（9番目）の箱に入った数値と、そのひとつ上（8番目）の箱に入った数値を比較して、下側（9番目）の方が小さければ入れ替える。

6) この比較を上から2番目の箱に辿りつくまで（3番目の箱と2番目の箱の比較）繰り返す。

最初に一番小さい数が入った箱を一番上に持ってくるための手順1)〜3)と、2番目に小さい数が入った箱を上から2番目に持ってくるための手順4)〜6)は、どこまで繰り返すかの違いのみで、実施することは全く同じです。

このように、3番目に小さい数、4番目に小さい数、、と順番に洗い出していき、9番目に小さい数を洗い出すまで実行（この時点で1〜8番目の数は確定しているので、比較するのは9番目の箱と10番目の箱のみ）すればソート完了です。

一番小さい値から順に次々と上に昇っていく様子が、泡が浮かんでいくように見えることから『バブルソート』と名付けられました。

数が大きい順（降順）にソートする場合は、下から順番に比較して、大きい数値の箱を上に持ってくるようにすればOKです。

また、上記の手順では、下から順番に比較していきましたが、上から順番に比較して、大きい数値の箱を下に持ってくるという比較方法でもOKです。この場合、まず最初に一番大きな数が入った箱を一番下に配置して確定、次に2番目に大きい数値の箱を洗い出して、下から2番目に配置する、、という流れになります。

Scratchで実装

Scratchのリスト「データ一覧」に格納された数値データを、上から昇順にソートします。

また、下から順に2つの項目(a, b)を比較していきますが、この値を入れ替える時、一時的に値を格納する変数cが必要になります。

– aとbの値を入れ替える手順 –

1) aの値をcへ
2) bの値をaへ
3) cの値をbへ

こちらがバブルソートの処理のスクリプト例です。

「?番目に小さい数」の変数にセットする値は、『現在、何番目に小さい数を探しているか』を示す数です。

バブルソートは、まず1番目に小さい数を選びだしますので、最初に「?番目に小さい数」に「1」をセットしています。
そして、1番目に小さい数がリストの一番上に配置されると1番小さい値は確定。次は2番目に小さい値を探しますので、「?番目に小さい数」をひとつカウントアップ（1 -> 2）しています。

データ一覧の項目数-1番目の数（10項目ある場合は、9番目に小さい数）が確定すれば、自動的に最後の値（一番大きい数）も確定しますので、データ一覧の項目数が10であれば1〜9番目に小さい数までが分かればOKです。
なので、小さい数を探す処理を、『データ一覧の項目数-1』回、繰り返しています（外側の繰り返し処理）。

「?番目の項目」の変数にセットする値は、『データ一覧リストの何番目の項目を比較するか』を示す数です。

まず、リストの一番下の項目から順に比較していきますので、最初にリストの項目数（一番下の項目となる）をセットしています。
そして、対象の項目と、そのひとつ上（「?番目の項目」−1番目）の項目を比較していきます。

この2項目の比較処理を一番下から順に行っているのが内側の繰り返し処理ですが、すでに確定した項目については比較する必要がありません（2番目に小さい数まで確定しているなら上から3番目の項目までが比較処理の対象）ので、繰り返し回数は「?番目に小さい数」を使って制御しています。

そして内側の繰り返し処理の中で、2項目を比較し、下側の項目の値の方が小さければ入れ替えを行っています。
上記の「aとbの値を入れ替える手順」に示した「c」に該当するのが「一時保管場所」という変数です。

サンプルプロジェクト

スクリプトの完成例がコチラ。

上記プロジェクトでは、リストの要素数と、各要素に設定する値を1から100の範囲でランダムに決めるところから実装しています。
リストのデータを作成後、スペースキーを押せばバブルソートを実行します。

ソートアルゴリズムには、他にも色々ありますので、興味があれば調べてみてください。