このスライド学習では、Google Colabを使用します。
Google Colabへは、次のリンクをクリックして移動しましょう。
また、ノートブックはIP02-10の続きを使用します。
それでは、まず通常の交換法のプログラムを変更して、比較回数をカウントして表示するように修正します。
情報活用編プラス
第3章「コンピュータとプログラミング」
IP02-10
実践プログラム③ 整列アルゴリズム 交換法
11. ✏️効率の良い交換法のプログラム ( 11 / 12 )
効率の良い交換法のプログラム
学習の目的
・効率の良い交換法のプログラム
効率の良い交換法のプログラム
以下のプログラムを新しいセルに入力して実行してください
# 交換法（バブルソート）の例
data = [1,2,3,4,8,5,6,7]
print("整列前:", data)
n = len(data) - 1 #データ数
compare_count = 0 # カウント用変数の初期化
while n > 0:
i = 0
while n > i:
compare_count += 1 #カウント用の変数に1を加算
# 隣り合う要素を比較
if data[i] > data[i+1]:
# 大きい方を右に入れ替え（交換）
w = data[i]
data[i] = data[i+1]
data[i+1] = w
i += 1
n -= 1
print("整列後:", data)
print("比較回数", compare_count)
実行結果
compare_countは、比較回数を計算する変数です。
これ、配列の内容から見てすぐ整列が完了してしまいますね。
でも、まだ改善は入れてないんですね。
そうですね。
比較回数は28回と表示されるはずです。
データ数が8個なので、8 × (8 - 1) ÷ 2の計算と合いますね。
では続いて、改良版のプログラムを見てみましょう。
以下のプログラムを新しいセルに入力して実行してください
data = [1,2,3,4,8,5,6,7]
print("整列前:", data)
n = len(data) - 1 #データ数
flag = 1 #①
compare_count = 0 # カウント用変数の初期化
while flag == 1 and n > 0: #②
i = 0
flag = 0 #③
while n > i:
compare_count += 1 #カウント用の変数に1を加算
# 隣り合う要素を比較
if data[i] > data[i+1]:
# 大きい方を右に入れ替え（交換）
w = data[i]
data[i] = data[i+1]
data[i+1] = w
flag = 1 #④
i += 1
n -= 1
print("整列後:", data)
print("比較回数", compare_count)
実行結果
あ、比較回数が13回に減った！！
でも、整列は完了しているね。
そうなんです。
これで、無駄な比較を行う必要はなくなりますね。
