情報活用編プラス
第3章「コンピュータとプログラミング」
IP02-10
実践プログラム③ 整列アルゴリズム 交換法
8. ✏️交換法プログラム ( 8 / 12 )
学習の目的
1.交換法のプログラム
2.比較回数による時間の違い
それでは、交換法のプログラムを作りましょう。
あ、空欄があるね。
空欄を埋めて実行してみようか！
以下のプログラムの空欄( a )に入るものを答えてください。
# 交換法（バブルソート）の例
data = [7, 3, 5, 1, 4]
print("整列前:", data)
n = len(data) - 1 #データ数
while n > 0:
i = 0
while n > i:
# 隣り合う要素を比較
if ( a ):
# 大きい方を右に入れ替え（交換）
w = data[i]
data[i] = data[i + 1]
data[i + 1] = w
i += 1
n -= 1
print("整列後:", data)
実行結果
ヒントとして、フローチャートも確認してみましょう。
交換法のフローチャート
( a )に入るものがわかったら、空欄を埋めたプログラムを実行して、実行結果を確認しましょう。
Google Colabへは、次のリンクをクリックして移動しましょう。
また、Google Colabでは新しいノートブックを作成し、名前をIP02-10としましょう。
空欄( a )を答えてください
プログラムの13行目〜15行目がデータの交換を行う部分です。
では続いて、降順にするプログラムについて考えてみましょう。
降順の場合の空欄( a )に何が入るか考えてみましょう。
そうか、昇順と降順は条件を変えるだけでいいんだ。
ってことは、上のプログラムの空欄( a )以外は全く一緒でもいいんだね！！
降順にするときの、空欄( a )を答えてください。
続いて、データ数を変更して、整列にかかる時間がどのくらい変化するか確認してみましょう。
以下のプログラムを実行しましょう。
import random
import time
# リストをランダムに生成する関数
def generate_array(size, low, high):
return random.sample(range(low, high+1), size) # 重複なし
# ===== メイン処理 =====
data = generate_array(1000, 1, 100000) # リストを作成
print("整列前の配列:", data)
start = time.time()
n = len(data) - 1 #データ数
while n > 0:
i = 0
while n > i:
if data[i] > data[i+1]:
w = data[i]
data[i] = data[i+1]
data[i+1] = w
i += 1
n -= 1
end = time.time()
print("ソート後の配列:", data)
print("処理時間: {:.6f} 秒".format(end - start))
このプログラムの内容を確認します。
import random
import timeランダムでデータを生成するrandomモジュールと、時間を計測するtimeモジュールをインポートします。
def generate_array(size, low, high):
return random.sample(range(low, high+1), size) # 重複なし
ランダムな値でリストを生成します。
（見本）generate_array(10,1,100)
第1引数：生成するデータの個数（見本ではリストを10個生成する）
第2引数：生成するデータの範囲の最小値（見本では最小値は1になる）
第3引数：生成するデータの範囲の最大値（見本では最大値は100になる）
第2引数が20、第3引数が100なら、20〜100の間の値のみでデータを生成します。
data = generate_array(1000, 1, 100000) # リストを作成
print("整列前の配列:", data)generate_array()関数を呼び出し、1,000件のデータを1～100,000の間でランダムな値でリストを作成します。
第1引数が1000なので、1000件のデータを生成します。
その後、生成したデータを表示します。
start = time.time()現在の時刻を取得します。
0.000001秒(1マイクロ秒)という細かい単位での時間になります。
n = len(data) - 1 #データ数
while n > 0:
i = 0
while n > i:
if data[i] > data[i+1]:
w = data[i]
data[i] = data[i+1]
data[i+1] = w
i += 1
n -= 1
交換法で整列します。
end = time.time()交換法の整列が完了した後の時刻を取得します。
print("ソート後の配列:", data)
print("処理時間: {:.6f} 秒".format(end - start))整列後の配列と、整列で経過した時間を表示します。
整列後に取得した時刻と、整列前に取得した時刻の差を求めることで、経過時間を求めます。
1,000件のデータを整列しました。
処理時間はどうだったでしょうか？
0.126697秒でした。
私は0.138780秒です。
0.1秒ちょっとで完了するって、とっても速いんだね！
そうですね。ランダムでデータが生成されるので、交換回数の差から多少の変化は出ますが、だいたい同じくらいの時間になります。
それでは、続いてデータ数を10,000件に増やしてみましょう。
9行目を以下の内容で書き換えてください。
data = generate_array(10000, 1, 100000)1,000を10,000に変更して、実行してみましょう。
少し時間がかかって心配になるかもしれませんが、少し待ってみてください。
30秒もかからないと思います。
プログラムを修正したら実行して、結果が出るのを待ちましょう。
実行してみて、経過時間はどうでしたか？
14.381963秒だったよ！！
私は14.283628秒だった。同じくらいだね
データ数は10倍だったけど、処理時間は100倍くらいになったね。
そうですね。では理由を考えてみましょう。
データ数は10倍なのに対し、処理時間が100倍近くになった理由を考え、説明してください。
データに対する、比較回数の計算式は、以下の通りです。
nが1000の時と、10000の時で、それぞれ比較回数を求めてみましょう。
最大 200 文字
※この再現版では提出は行いません（送信先は未接続です）
