文科省の情報Ⅰの教員研修用教材，選択ソートもあれれ・・・

　例年より早い桜の落花。しかし，今はソメイヨシノの次に八重桜が満開。散った桜は鮮やかな緑の葉になっているし，見出し写真の柿の葉もあざやかな緑。
　入学式が終わって，新学期がスタート。大学入試共通テストへに情報Ⅰが入ることが決まって，さあ大変，と思っている学校は多いだろう。早速，文科省の教員研修用教材をダウンロードして勉強しようと思っている人もいるはずだ。
　が，ちょっと待って。書かれているプログラムには間違いがあるから，修正されるまで待ったほうがいいかも。それより，拙作の入門書をダウンロードして読まれたほうが・・・（宣伝）
　それはそうと，何が間違いかというと，以前指摘したクイックソートだ。さらに
その前にある選択ソート。クイックソートを指摘してから10日以上経っている。つまり，以前は気がつかなかったのが，今ごろ気がついたわけだ。プログラムは正しい結果を導き出すので，いわゆるバグとはいえないのかもしれない。しかしバグ＝虫がいないわけではない。死んでいるだけ。

　大学入試センター試験の「情報関係基礎」の過去問を教材化する，という note を書き始めた。2008年の問題が「並べ替え」である。扱っているのはバブルソート。簡単なアルゴリズムだが，これに「改善案」が入るのが面白い。
　これを教材化する案を書いていて，Pythonの「インデックスは0開始」と，range(a,b) は a以上b未満，というのに結構悩まされた。「情報関係基礎」のコードはインデックスが１開始なのでそこを読み替えなければならない。それだけなら何ということはないのだが，j と i をインデックスとして，for j in range()　の中に for i in range()　が入るネスティングになっている。しかも，j は 要素数-1 から０ まで，i は ０ から j-1 までという逆順。すでにちょっとややこしくなっている。詳しくは，いずれ「情報関係基礎過去問を教材化する：2008年バブルソート」として公開する予定だ。

　さて，このバブルソートを検討していて，選択ソートではどうなるか，を考え，コーディングしてから，文科省の研修用教材にあったもので「答え合わせ」をしてみた。すると，あれ？　違うぞ。となった。該当箇所はこうなっている。

■選択ソート
選択ソートはリスト内のデータから最小値を探索し，最小値から順に取り出すことで並べ替えを実現するアル ゴリズムである。(図表8参照)

プログラム例はこうなっている。

どこがおかしいかおわかりだろうか。
前述の通り，このプログラムは正しい結果を出すので，いわゆるバグはない。
おかしいのはアルゴリズムである。

アルゴリズムのどこがおかしいのか，また，そのおかしいアルゴリズムでなぜ正しい結果が出るのか，それを説明していこう。

選択ソートの原理

　選択ソートというのは，研修用教材の説明にある通り，「最小値を探索し，最小値から順に取り出していく」（昇順の場合）というものだ。実際には「取り出す」のではなく，左から順に置き換えていく。最大値なら降順になる。
　ここで，「最小値を探索し・・・取り出していく」で２つの方法が考えられる。
（その１）「2つずつ比較しながら入れ替えていく」
（その２）「最小値を求めてから入れ替える」

具体的に示そう。少し長いが，初めての人がいることを考慮して書いた。

（その１）「2つずつ比較しながら入れ替えていく」

基準となるインデックスを i ，比較するインデックスを j とすると，
i は 0 から始めて 3 まで，j は i + 1 から始めて 4 まで動かすことになる。
リストの要素の数は５でインデックスは０から４までだ。i は最後の4の手前の3まで変化させる。

もう一度研修用教材のコードを見てみよう。

どこがおかしいかおわかりだろう。len(a) は a の要素の数（17） である。したがって，インデックスの最後の番号は16。range(0, len(a), 1) だと，０から 16 までということになる。しかし，i は 0 から始めて16までではなく，その手前の15まで変化させるのだから，for i in range(0, len(a)-1, 1): でなければならない。

では，アルゴリズムが間違っているのになぜ正しい結果が出るのか。

もとのコードで最後の場面を考えよう。i は len(a) -1 すなわち 16 で，for j in range( i+1, len(a), 1 ) とすると，j は17から始めることになる。すると，インデックスの最大値を超えるからエラーになるはずだ。
ところがそうならない。なぜかというと，i が len(a) -1 のとき，range( i+1, len(a), 1 ) のシーケンス（数列）は空になるからだ。Pythonでの for j in seq は seq の中身を順に取り出しながら繰り返す。seq の中身が空なら何もしないのだ。試しに次のコードを実行してみよう。

何も起こらない。range(17, 17, 1) がどんなシーケンスを作るか確かめよう。

[ ] すなわち，空リストが出力されていくことが確かめられた。 

結果として，最後の a[16] と a[17] の比較は行われなかったのである。
このことは，他の言語ではどうなのだろう。for による繰り返しの構文は異なるが，JavaScript , Ruby , C でも同じだった。結果として，最後の a[16] と a[17] の比較は行われない。

とはいえ，やはり正しいアルゴリズムに基づいて書くべきだろう。

（その２）「最小値を求めてから入れ替える」

　選択ソートでは，ふつうこちらの方法を使うようだ。いちいち入れ替えるのでなく，最後まで検索して最小値を求めてから入れ替えをする。この表現は，研修用教材の表現そのものだ。

　値が最小値になるインデックスを m とする。はじめは m = i  としておく。
j を i+1 から始めて，a[m] と a[j] を比較し a[m]>a[j] なら m = j とする。j が最後まで行くと，値が最小値のインデックス m が確定するので a[i] と a[m] を入れ替える。
　入れ替える回数が少なくなるわけだ。
コードを示そう。

def selectionsort(a):
   for i in range(0, len(a)-1):
       m = i
       for j in range(i+1, len(a)):
           if a[j] < a[m]:
               m = j
       temp = a[i]
       a[i] = a[m]
       a[m] = temp

a = [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
print(" ソート前 ", a)
selectionsort(a)
print(" ソート後 ", a)

 これで，入れ替えの回数がどのくらいになるか調べてみよう。
理論的には，次のようになる。要素の数を n とすると，
比較の回数は，(n-1)+(n-2)+・・・2+1 = n(n-1)/2 なので n=17 なら136回。
比較の都度入れ替えも行えば入れ替えも136回だ。
最小値を求めてからだと，比較の回数は同じで，入れ替えは i の回数と同じで 15 回になる。
さらに，i と m が異なるときだけ入れ替えを行えば，入れ替えの回数はさらに減る。

【課題】適当な変数を用意し，これらの回数をカウントするコードを追加せよ。