【高等学校情報１】ソートアルゴリズム（選択ソート・クイックソート）Pythonプログラミング/教員研修用教材 学習15

◆◆はじめに◆◆

第３章　コンピュータとプログラミング
学習１５　ソートアルゴリズム（選択ソートとクイックソート）

https://www.mext.go.jp/a_menu/shotou/zyouhou/detail/1416756.htm

別動画でアップしているPython超入門講座は一通り理解している前提で進めています。教員研修用教材に完全に準拠した形で解説しています。（P128～）

E.V.ジュニアさんのブログ内容を参考に作成させて頂きました。
（ありがとうございます）

上記の通り、教員研修用教材のプログラムだと虫（バグ）がいるっぽいので、E.V.ジュニアさんの修正案プログラムを利用させて頂きました。

アルゴリズム把握をメインとして、Pythonプログラム部分はざっくり説明にしています。

クイックソートは考え方が結構難解ですが、
どうやって教えれば伝わるかで一日頭を抱えていました・・
なんとか動画にできましたが、必要に応じて今後改善していきます。

◆◆今後の予定◆◆

夏までに、教員研修用教材(情報１）の内容を一通り動画で説明した後、
（秋には教科書が手に入る前提で）教科書を見て足りない部分の補足講座をどんどん追加していく予定です。（言語はPythonのみを扱います）

ただ、共通テストは疑似言語なので、Pythonの深堀より、早めに情報関係基礎の過去問ベースの内容に切り替える予定。
（皆が一生懸命プログラミング勉強する理由は、「大学入試科目だから」という認識）

来年４月からは、多分、実際の高校生からYouTubeに対してコメント頂けはじめると思うので、さらなる改善（補足講座）と定期試験対策講座を配信していきたいと考えています。

◆◆動画解説◆◆

情報処理技術者試験・高校情報教科対策の突破口ドットコム

◆◆文字おこし◆◆

前回は探索アルゴリズムについて解説したから、今回はソート（並び替え）アルゴリズムについて説明するね。
リストなどの中を昇順，降順に並べ替えることをソートといって，選択ソートやクイックソートなどがある。

まず、選択ソートはリスト内のデータから最小値を探索し，最小値から順に取り出すことで並べ替えを実現するアルゴリズムなんだ。

１７個の要素があるリストaをソートしていこう。
はじめの基準は一番左側の添字[0]の部分になる。
添字0の要素である７をそれより左側にあるリストの値と比較していく。
７より小さい値として初めに引っかかるのは、添字11の５になる。
その時点での最小値は５になるから、添字11と残りのリストを比較していく。
次に５より小さいのは添字14の４となるから、基準が添字14の４となる。
次に４より小さいのは添字15の２となるから、基準が添字１５となる
そして、２より小さいのは添字16の１になる。この時点でリスト内を全部比較したから
添字０の値と最小値である、添字16の１とを入れ替える。
ただ、添字１６の値をそのまま添字０に入れてしまうと、添字０の７が上書きされて消えてしまうから、一時的に値を退避する領域が必要になる。
添字０の７を一次領域にコピーして、最小値の添字16の値を添字０に上書きして
temp領域の内容を添字１６に上書きする。結果だけで見ればひっくり返しただけだけど、値の交換はワンクッション必要なことを覚えておこう。

a[0]の最小値は確定したから、今度は隣のa[1]の値を基準にして、最小値を調べていく。
比較対象が１つ減っただけで、やることはさっきと同じ。
２２と添字２の１１を比較して１１の方が小さいから、これが比較対象となる。
添字２の１１を基準に右側を順番に見ていって、添字１０の１０が１１より小さいから、比較対象が変わる。次に添え字１１の５が１０より小さいから比較対象が変わる。
次に添字１４の４が５より小さいから比較対象が変わる。
次に添え字１５の２が４より小さいから、添え字１５が比較対象になる。
そして最後の添字１６の値は７だからこの時点で最小値が添字１５の２となる。
添字１の２２を退避して　２を添字１の場所に持って行って　退避した２２は添字１５に持ってくる。
これを、添字１５まで繰り返せば並び替えは完了する。

これをPythonプログラムであらわすとこんな感じになる。

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)

流れは今説明したとおりだけど、親ループ１回分値を当てはめてみていこう。

――
関数 selectionsortの引数はさっき演習したのと同じリストを受け渡す。

そして、初めfor文は　添字１５まで繰り返す。添字１５までおこなったら最後の添字１６の値は確定しているから、一番最後の添字までループする必要はない。

そして　変数ｍに変数iの値ここでは初回なので０を代入する。
このｍは暫定的な最小値を持つ要素の添字を保持する。
そして、子のfor文に入る。
スタートは添字iにプラス１した値からリストの最後まで繰り返す。
暫定最小値より小さい値があった場合は、その比較先の添字はjに入っているから、暫定最小値を示す添字のmに代入する。
リストの最後まで行ったらループを抜けて
添字i ここでは０の物を一次領域のtempに退避し、そこに最小値を上書き、tempに退避した値は最小値があった場所に上書きする。
そして、次の添字１について同じ処理を繰り返す。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
クイックソートはリスト内の一つのデータを基準として，大小２つに分割した後，分割したデータに対して更に同じ処理を再度行うことにより並べ替えを実現するアルゴリズム

言葉だけではわからない思うから具体例で説明するね。

このような８つの要素を持つリストaがあったとする。
まずは、軸となる基準値を決める。決め方は色々あるけど、今回は下限の添字と上限の添字を足して２で割った位置にあるものを基準値とすることにする。もし、小数点以下が出た場合は切り捨てを行う。

まず下限の添字は０、上限の添字は７だから（０＋７）÷２をして３．５となり、小数点以下を切り捨てて、添字３の場所にある３４を基準値とする。

左側にある値は基準値より小さいこと、右側にある値は基準値より大きいことが前提で
左側は下限の添字を１ずつ増やしながら、右にシフトしながらチェックしていく。
右側は上限の添字を１ずつ減らし左シフトながらチェックしていく。

まずは下限の方で、基準値以上になっているものが存在するまでシフトしていく
そうしたら添字3の34が基準値以上になるのでここで一旦ストップする。

上限の方は、基準値以下のものが存在するまで、左にシフトしていくんだけど、
はじめの添え字７の１３が基準値の３４よりも小さいから、これが該当する。

これで、今見つかった３４と１３の値を交換する。
さっきの選択ソートと同じように一度temp領域に退避しないと値が消えてしまうから注意しよう。

交換がおわったら、次の添字から同様のチェックを再開する。
下限は添字５の５２が基準値の３４以上なのでここで処理をストップする。

上限側は添字６の２６が基準値以下なので　５２と２６を交換する。

次の処理で上限と下限がお互いを追い越すので、１回目のグループ分けを行う。

今回のグループ分けは　基準値の３４より小さいグループの添字０から５の部分と　基準値以上グループ、添字６と７の部分に分けられる。

その分けたグループそれぞれに対して同様の処理を行っていく。

左側のグループの基準値を求めよう、下限の添字は０上限の添字は５なので
添字２の１１が基準値となる。

下限の右シフトは基準値の１１以上となるものがあったら、一旦ストップする。
上限の左シフトは基準値の１１以下になるものがあったら一旦ストップして
その値同士をひっくり返す。
添字１の２２　と添字２の１１が該当するので、それをひっくり返す。
ここで、添字０のグループと添字１から５までのグループに分解できる。

添字０のグループはこれ以上分解できないところまできたので、並び替えとしては完了。
グループの要素が２以上あるものに対して、グループ要素が１になるまで繰り返す。

この範囲を狭めながら同じことを繰り返している処理を再帰呼び出しとか、再帰処理という。

簡単にPythonプログラムを見ていこう

def quicksort(a, start, end):
   m = int((start+end)/2)
   i = start
   j = end
   key = a[m]
   while i <= j: 
       while a[i] < key:
           i = i + 1
       while a[j] > key:
           j = j - 1
       if i >= j:
           break
       temp = a[i]
       a[i] = a[j]
       a[j] = temp
       i = i + 1
       j = j - 1   
   if start < i - 1:
       quicksort(a, start, i - 1)
   if end > j + 1:
       quicksort(a, j + 1, end)
      
a = [7, 22, 11, 34, 17, 52, 26, 13]
print(" ソート前 ", a)
quicksort(a, 0, len(a)-1)
print(" ソート後 ", a)

関数quicksortは並び替えたいリストa 、下限の添字と上限の添字を引数とする。

mは基準値のありかをしめす添字
iは下限の添え字、jは上限の添字
keyは基準値

そして、下限が上限以上になるまで繰り返す。

この部分は、下限の右シフト、基準値以上の値があったらストップする
この部分は、上限の左シフト、基準値以下の値があったらストップして
お互いの数を入れ替える。

そして、この部分はそれぞれ分けられたグループに対して、同じ処理を行う再帰処理になる。
注意してみてほしいのは、quicksortの関数内から自分自身の関数であるquicksortを呼び出していること。これを再帰呼び出しという。こうすることでプログラムを簡潔に記述できるんだ。

クイックソートのアルゴリズムがややこしいけど、流れを把握しておこう。

＝＝＝＝＝

【メモ】途中経過トレース

print(a, start, i - 1, j + 1, end)

情報処理技術者試験・高校情報教科対策の突破口ドットコム