バブルソートは易しいか

　ソーティング（並べ替え）の中でも，バブルソートは最も基本的なものだろう。大学入試センター試験「情報関係基礎」では，2008年に出題されている。プログラミングの学習では初期段階で扱うことが多い。今の言語では sort() という関数が用意されていたりするので，これを使うことはほとんどないが，使うかどうかではなくアルゴリズムの練習になる。
　ポイントは２つある。

(1) 原理を理解できるか
(2) 「２つの値の入れ替え」ができるか

　大学入試センター試験「情報関係基礎」の問題はかなり丁寧で，(1) について，具体例をあげながら説明し，その中に空欄を作って問題としている。また，プログラムコードは，まず (2) の値の入れ替えから始まる。
　まず，(1) の説明はこうなっている。データはテストの得点で，降順に並べる。

　並べ替えは次のように行う。まず，全員の得点（と名前）を左から一列に並べる。第１段階として，左端から順に隣り合う二人の得点を比較し，左の人の得点の方が低いときには二人の順番を入れ替える。これを右端の人まで繰り返し，最も得点が低い人を確定する（第1段階の終了）。第２段階以降も，第１段階と同様，左端から順に同じ処理を行い，得点が低い人を順番に確定していく。

このあと，具体例を示してこのアルゴリズムを確認する。次のような図も載せてある。

プログラムコードは，まず「入れ替え」から。
説明文として，次のことが書いてある。

配列 Namae と配列 Tokuten の，i 番目の人と i+1 番目の人を表す要素をそれぞれ入れ替えるための手続きは図3のようになる。ここで，変数 n は，名前を一時的に保持するための変数であり，変数 t は得点を一時的に保持するための変数である。

02 行目がまったくの空白だから，やったことがなければ難しいかもしれない。

　昨年，バブルソートを期末テストで出題した。センター試験の問題をベースにしている。

　リスト Data にN個の数値データが入っている。この中身を昇順（小さい方から大きい方へ）に，次のアルゴリズムで並べ替える。
(1) m=1 から始める。入れ替えを行ったときの番号を n とし，はじめは n=0 とする。
(2) Data_m と Data_(m+1) を比較し，Data_m > Data_(m+1)なら入れ替える。
(3) 入れ替えをおこなったとき，その番号 m を n に代入する。
(4) m を１つ進めて (2) (3) を行う。
(5) はじめは，変数 saigo を N-1 にしておく。初めから saigo まで(2)の比較をしていく。最後まで比較が終わったら，そのときの nの値をsaigo の値とする。
(6) 入れ替えが行われたならば，(1)に戻って比較することを繰り返す。
　このアルゴリズムにもとづいてプログラムを作った。
01: saigo=N-1;
02: while(saigo>0,
03:   n=0;
04:   repeat(saigo,m,
05:      if(Data_m > Data_(m+1),
06:          w=Data_m;
07:          Data_m=
08:          Data_(m+1)=
09:          n=m;
10:      );
11:    );
12:
13:  );
　
【問題】次の各問いに答えよ。（15点）
(1) 上のプログラム中，07,08行目の＝の右辺と12行目に書くべきコードを書きなさい。

06〜08 が入れ替えだが，「入れ替える」としか書かれておらず，アルゴリズムの説明はないので「何をしているのか」を考える必要がある。
　正答率は，07行目が 38%，08行目が 19%だった。
なお，12行目は (5)の説明「nの値をsaigo の値とする。」でわかるかと思ったのだが，正答率はわずか 7% であった。
　正答率が低い理由として考えられるのは，「問題文に書いてあること，プログラムでやっていることがわからない」ということだ。言い換えると，問題文で説明されている並べ替えのアルゴリズムが理解できない，ということだ。
これは，「問題文の説明がわかりにくい」ということもあるかもしれない。

　今年はプログラミングの基礎の時点で，練習問題としてやらせてみた。変数，リストの扱いをひととおりやったあとだ。

(1) 値の入れ替え
　変数 a と b の値を入れ替える。まず a と b に適当な値を代入しておく。左端はCindyScriptエディタの行番号。１行目にはコメント文で HRNO と氏名を書く。
　　2: a=3;
　　3: b=5;
　a と b の値を入れ替えるために，b=a としてしまうと，b の値が 3 となり，5 が消えてしまう。そこで，b の値を他の変数にコピーしておく。
　次の4〜6行目で手順を // でコメント文にしたので，それに対応するコードを書きなさい。コメント文は書かなくてよい。
　7行目で，a,b の値をリスト [a,b] にしてコンソールに表示する。[5,3] となればよい。
　　4:                        // b の値を w に代入する
　　5:                        // a の値を b に代入する
　　6:                        // a にコピーしておいた w の値を代入する
　　7: println([a,b]);

このあとの並べ替えではリストを使い，次の右辺を書くようになっている。説明のコメント文はないので，そのための事前練習である。
　　12: w=
　　13: int_(k+1)=
　　14: int_k=

さて，結果はどうか。
4,5,6 行が書けなかった生徒が１割程度。間違いとしては次のものが多数。
　　4: w=5;
　　5: b=3;
　　6: a=w;

たしかに
　　2: a=3;
　　3: b=5;
だから
　　4: w=5;        // b の値を w に代入する
　　5: b=3;         // a の値を b に代入する
にはなっている。しかし，それにしては，
　　6: a=w;        // a にコピーしておいた w の値を代入する
ができているのはなぜだろう。
おそらく「変数の概念」がわかっていないのだろう。
しかし，ここができなかった生徒でも

12: w=
13: int_(k+1)=
14: int_k=

はできている。
なぜか。
ひとつは，「具体的な値ではないから」ということがあろう。
しかし，おそらく「相談して，できた生徒に聞いた」のではないかと思われる。相談は自由としているからだ。
しかし，ここができているのに，戻って 4,5 行目を直す，ということはしていない。つまり，本当はわかっていないという可能性がある。

さて，先ほど，

これは，「問題文の説明がわかりにくい」ということもあるかもしれない。

と書いた。センター試験の問題は，くどいほど丁寧に書かれている。具体例のところで穴埋めにすれば，理解の度合いを確認する問題にできるということもあるだろう。

　並べ替えのアルゴリズムをどのように説明するのかは意外に難しいことなのかもしれない。
　というのも，先日見本が届いた某社のテキストを見てあきれてしまったからだ。
本の末尾の方に，付録としてバブルソートが載っている。
　この本ではそれぞれの例題に対して「シナリオ化」と「フローチャート」が並立して書かれているのだが，この「シナリオ化」がわかりにくいのだ。左が「シナリオ化」で，右のフローチャートに対応している。

フローチャートのループＢ，Ｃの説明が「シナリオ化」では次のようになっている。（上の図のものをあらためて書く）

Ｂ
・変数 p に入力したデータ数を記憶した変数 n の値を記憶する。（配列の後ろから位置を確定させるため）
・配列 Lst の p 番目から順番に１つずつ位置を確定する（ p の位置を１つずつ減らす）。
・変数 p が１になるまで作業を繰り返す。
Ｃ
・変数 a に 1 を記録する（基準となる配列の添え字 a は 1 からはじまるため）。
・変数 a は 1,2,3・・・というように順番に１つずつ変化させる（ a の値を1ずつ増やす）。
・変数 a が 変数 p-1 と同じになった時点で作業を終了する（基準となる配列の添え字が比較するデータ数と同じになった場合，比較できなくなるため）。
E
・配列の基準が大きい場合，Svを活用し，Lst(a) と Lst(a+1) の値を交換する。
　　　　　　　　　　　出典：実例で学ぶ　プログラミングの基礎（実教出版）

どうだろう，変数 p が何のために必要なのかわかっただろうか。
E の説明も「Svを活用し」をどのように「活用」するのか，まったく不明だ。
フローチャートをみれば使い方がわかるが，代入の向きが逆だ。
これでは，Lst(a+1) → Sv 　を見て， Lst[a+1] = Sv 　と書く生徒が続出するだろう。
Sv ← Lst(a+1)　とすべきだ。プログラミングの A = B は 「AにBを代入する」のだから。
「 Lst(a+1) → Sv でも同じではないか」と思う人は，現場で指導してみればわかる。

ついでに，このフローチャートについても一言苦言を呈しておこう。
２つの繰り返し処理がネストされているのだが，その対応関係が，このフローチャートではわかりにくい。「この」どころか，フローチャートではネスティングした繰り返し処理や条件判断はわかりやすく記述できないのだ。

　repeat(n,p,step->-1,
        repeat(p-1,a,
            処理
        );
    );

というコードの方がよほど見やすい。フローチャートを書く意味はまったくない。

　さて，これは審査用見本である。できたばかりで，まだどこも採用には至っていない。教科書会社のセールスマンを通して，これはよくないといってやった方がいいものだろうか。

追記：
　期末テストで出した問題の saigo は，「情報関係基礎」の問題の続きにある，改良版のものです。データ数が N のとき，基本的なバブルソートでは，１回目は Nまで，２回目は N-2 まで，と，隣接する数の比較をしていく場所を減らしていきますが，改良版では，どこまで入れ替えをしたかを変数 saigo に記録することで，比較回数を減らします。つまり，後ろのいくつかがすでに昇順（降順）になっているなら，そこはやらなくてよい，ということです。
　　　　　　　　　　　　　　　　　　　　2020.11.24

追記２：訂正
　「事例でまなぶ　プログラミングの基礎」は，2019年3月に発売されていた。採用されているかどうかは不明。