この章では、アルゴリズムの基本である並び替えについて学びます。
並び替えとは、データを昇順や降順に整列することです。
例えば、数値の配列を昇順に並び替える場合、数値が小さい順に並べ替えることになります。
交換法は、データを並び替えるアルゴリズムの一つです。
交換法は、隣り合うデータを比較して、条件に合わない場合に交換を行うことでデータを整列します。
交換法の実装として「数値が並ぶ配列list1を昇順に並び替える」プログラムを作成することを考えてみましょう。今回はlist1 = [88, 65, 43, 27]とし、これを[27, 43, 65, 88]に並び替えることを目標とします。
実装の目標としては、配列list1の先頭から順に格納されている数字を見ていき、隣り合う数字を比較して、条件に合わない場合に交換を行うことで、配列list1を昇順に並び替えることが考えられます。
話を簡単にするため、要素数が2つの配列[..., ...]について考えます（ただし、...、...はどちらも数値）。
この配列を昇順に並び替えるには、各要素の数値を比較して、
list[0] > list[1]（配列の1番目の要素のほうが配列の2番目の要素より大きい）の場合 → list[0]とlist[1]の要素を交換するlist[0] <= list[1]（配列の1番目の要素のほうが配列の2番目の要素より小さい、あるいは同じ）の場合 → そのまま（並び替える必要がない）という条件を満たすようにすればよいでしょう。list1 = [88, 65]と仮定して、この操作をするプログラムは以下のようになります：
list1 = [88, 65]
if list1[0] > list1[1]: # 88 > 65 なので条件を満たし、3行目以降が実行される
temp = list1[0] # 1.
list1[0] = list1[1] # 2.
list1[1] = temp # 3.このプログラムのifのインデント内では、以下の流れで処理が行われます：
ifのインデントに入る前の各変数の値
| temp | list1[0] | list1[1] |
|---|---|---|
| 88 | 65 |
temp = list1[0]で変数tempにlist1[0]の値（88）を一時的に保存（tempはtemporary（一時的な）の略）
| temp | list1[0] | list1[1] |
|---|---|---|
| 88 | 88 | 65 |
list1[0] = list1[1]でlist1[0]にlist1[1]の値を代入
| temp | list1[0] | list1[1] |
|---|---|---|
| 88 | 65 | 65 |
list1[1] = tempでlist1[1]にtempの値、すなわち元々のlist1[0]の値（88）を代入
| temp | list1[0] | list1[1] |
|---|---|---|
| 88 | 65 | 88 |
list[0]およびlist[1]の、最初と最後の表の値を見比べると、見事にlist1[0]とlist1[1]の値を交換できていることが分かります。このようにして、配列の2つの要素を昇順に並び替えることができます。
配列の長さが2であれば、上記のプログラムで昇順に並び替えることができます。しかし、配列の長さが3以上の場合、どのようにすればよいでしょうか？
「隣り合う2つの数字を比較して、昇順に並び替える」という処理を、配列に適応することを考えてみましょう：
[88, 65, 43, 27]の最初の2つ（1番目と2番目）の数字88と65に処理を適応すると、[65, 88, 43, 27]となります。[65, 88, 43, 27]の次の2つの数字（2番目と3番目）88と43に処理を適応すると、[65, 43, 88, 27]となります。[65, 43, 88, 27]の次の2つの数字（3番目と4番目）88と27に処理を適応すると、[65, 43, 27, 88]となります。この処理を表にまとめると以下のとおりです（便宜上、処理の流れを1-n回目と表記します）：
| 流れ | 適応箇所 | 交換前 → 交換後 |
|---|---|---|
| 1-1回目 | 1番目と2番目 | 88, 65, 43, 27 → 65, 88, 43, 27（交換） |
| 1-2回目 | 2番目と3番目 | 65, 88, 43, 27 → 65, 43, 88, 27（交換） |
| 1-3回目 | 3番目と4番目 | 65, 43, 88, 27 → 65, 43, 27, 88（交換） |
ゆえに、配列の先頭から順に「隣り合う2つの数字を比較して、昇順に並び替える」という処理を、1つずつずらして配列の末尾まで繰り返すと、配列の中で 最も大きい数字が最後尾に移動する ことになります。1つずつずらすことによって配列の中のすべての要素が比較され、最も大きい88が最後尾に移動しました。
では、この状態でもう一度配列の先頭から順に「隣り合う2つの数字を比較して、昇順に並び替える」という処理を繰り返すとどうなるでしょうか？：
[65, 43, 27, 88]の最初の2つ（1番目と2番目）の数字65と43に処理を適応すると、[43, 65, 27, 88]となります。[43, 65, 27, 88]の次の2つの数字（2番目と3番目）65と27に処理を適応すると、[43, 27, 65, 88]となります。[43, 27, 65, 88]の次の2つの数字（3番目と4番目）65と88に処理を適応すると、[43, 27, 65, 88]となります。この処理を表にまとめると以下のとおりです（2周目なので、処理の流れを2-n回目と表記します）：
| 流れ | 適応箇所 | 交換前 → 交換後 |
|---|---|---|
| 2-1回目 | 1番目と2番目 | 65, 43, 27, 88 → 43, 65, 27, 88（交換） |
| 2-2回目 | 2番目と3番目 | 43, 65, 27, 88 → 43, 27, 65, 88（交換） |
| 2-3回目 | 3番目と4番目 | 43, 27, 65, 88 → 43, 27, 65, 88（変化なし） |
ゆえに、配列の先頭から順に「隣り合う2つの数字を比較して、昇順に並び替える」という処理を、1つずつずらして配列の末尾まで繰り返すと、配列の中で 2番目に大きい数字が最後から2番目に移動する ことになります。このように、「配列の先頭から順に『隣り合う2つの数字を比較して、昇順に並び替える』という処理を、1つずつずらして配列の末尾まで繰り返す」という処理を繰り返すごとに、配列の末尾からその繰り返した回数分だけ大きい数字が昇順で並ぶようになります。
すなわち、配列の長さが4 であれば、「配列の先頭から順に『隣り合う2つの数字を比較して、昇順に並び替える』という処理を、1つずつずらして配列の末尾まで繰り返す」という処理を 4回繰り返せば かならず昇順に並び替えが完了するということです。各繰り返しごとに、比較処理は3回（配列の長さ - 1 回）行われるので、全体としては比較処理が 4 ✕ 3 = 12 回行われることになります。
コードの実装では以下のようになります：
list1 = [88, 65, 43, 27]
length = len(list1)
for i in range(length): # 配列の長さだけ繰り返す（今回は4回）
for j in range(length - 1): # 各繰り返しごとに、比較処理を「配列の長さ - 1」回行う（今回は3回）
if list1[j] > 「ア」: # 比較処理
temp = list1[j]
list1[j] = 「ア」
「ア」 = temp上記のプログラムの「ア」の部分にはどのようなコードを入れればよいでしょうか？
答え：list1[j+1]
list1 = [88, 65, 43, 27]
length = len(list1)
for i in range(length): # 配列の長さだけ繰り返す（今回は4回）
for j in range(length - 1): # 各繰り返しごとに、比較処理を「配列の長さ - 1」回行う（今回は3回）
if list1[j] > list1[j+1]: # 比較処理
temp = list1[j]
list1[j] = list1[j+1]
list1[j+1] = temp隣接する2つの数字を比較して、条件に合わない場合に交換を行う処理を行うため、list1[j]とlist1[j+1]を比較します。
list1[j-1]も、隣接する数字ではありますが、jはrange(length - 1)で定義されているため、jが0のときj-1は-1となり、配列の範囲外になってエラーを起こしてしまいます。
また、iはそもそも比較のためではなく、「配列の先頭から順に『隣り合う2つの数字を比較して、昇順に並び替える』という処理を、1つずつずらして配列の末尾まで繰り返す」という処理自体を繰り返すための変数であるため、list1[i-1]やlist1[i+1]を比較に使うことは不適です。
実は、上記のプログラムは冗長な部分があります。2周目の比較処理の表をもう一度見てみましょう：
| 流れ | 適応箇所 | 交換前 → 交換後 |
|---|---|---|
| 2-1回目 | 1番目と2番目 | 65, 43, 27, 88 → 43, 65, 27, 88（交換） |
| 2-2回目 | 2番目と3番目 | 43, 65, 27, 88 → 43, 27, 65, 88（交換） |
| 2-3回目 | 3番目と4番目 | 43, 27, 65, 88 → 43, 27, 65, 88（変化なし） |
「2-3回目」の処理に着目してください。[43, 27, 65, 88]の3番目と4番目の数字65と88を比較していますが、末尾にはすでに1周目の処理で最も大きい数字である88が移動しています。そのため、65と88を比較するまでもなく、3番目と4番目の数字はすでに昇順に並び替えられていることがわかります。
では、3周目の比較処理はどうでしょうか？：
| 流れ | 適応箇所 | 交換前 → 交換後 |
|---|---|---|
| 3-1回目 | 1番目と2番目 | 43, 27, 65, 88 → 27, 43, 65, 88（交換） |
| 3-2回目 | 2番目と3番目 | 27, 43, 65, 88 → 27, 43, 65, 88（変化なし） |
| 3-3回目 | 3番目と4番目 | 27, 43, 65, 88 → 27, 43, 65, 88（変化なし） |
上記の表は、3周目の比較処理を示しています。この「3-3回目」の処理を見ると、3番目と4番目の数字65と88を比較しても、末尾にはすでに2周目の処理で2番目に大きい数字である65が移動しています。そのため、65と88を比較するまでもなく、3番目と4番目の数字はすでに昇順に並び替えられていることがわかります。加えて、「3-2回目」の処理も同様に、2番目と3番目の数字43と65を比較しても、すでに2周目の処理で2番目に大きい数字である65が、末尾から2番目に移動しているため、比較するまでもなく昇順であることがわかります。
すなわち、
というわけで、各週ごとに比較処理が必要な回数は1回ずつ減り、4周目に至ってはなんと実行する必要がないということになります。
という事がわかりました。これを反映すると、プログラムは以下のようになります：
list1 = [88, 65, 43, 27]
length = len(list1) # 4が入る
for i in range(length - 1): # 繰り返しの回数は1回少なくて良い（今回は3回）
for j in range(「ア」): # 各繰り返しごとに、比較処理を行う
if list1[j] > list1[j+1]: # 比較処理
temp = list1[j]
list1[j] = list1[j+1]
list1[j+1] = temp上記のプログラムの「ア」の部分にはどのようなコードを入れればよいでしょうか？
答え：length - 1 - i
list1 = [88, 65, 43, 27]
length = len(list1) # 4が入る
for i in range(length - 1): # 繰り返しの回数は「配列の長さ - 1」回で十分（今回は3回）
for j in range(length - 1 - i): # 各繰り返しごとに、比較処理を行う
if list1[j] > list1[j+1]: # 比較処理
temp = list1[j]
list1[j] = list1[j+1]
list1[j+1] = temp繰り返しの回数は、配列の長さ - 1 回で十分であるため、range(length - 1)としています。
各繰り返しごとに、比較処理を行う回数は、繰り返しの回数に応じて
と表現でき、range(length - 1 - i )と表せます。
上記プログラムでは、比較処理の回数が繰り返しの回数に応じて減少するため、全体としては比較処理が 3 + 2 + 1 = 6 回で済み、回数を半減することができました。
今回は「交換法」の実装を通して、並び替えのアルゴリズムについて学びました。
交換法は、隣り合うデータを比較して、条件に合わない場合に交換を行うことでデータを整列する並び替えのアルゴリズムです。並び替えアルゴリズムには他にも選択法や挿入法などがありますが、交換法はその中でも最も単純なアルゴリズムの一つです。
これにて実験の学習内容は終了となります。お疲れ様でした。
学習時間の終了後には、15分ほどの確認テストを実施する予定です。
学習時間の終了まで、学習内容の復習や休憩などにあててお待ち下さい。