Python学習シート（ソートアルゴリズム編） ２　選択ソート（select sort） 課題2-1 (1) #選択ソート（降順） #プログラム中の@〜Jはアニメーション用のプログラムです #アニメーション表示なしで高速に実行するためには@〜J（最小でF〜J）をコメント文にしてください。 import numpy.random as rd # numpy.randomモジュールをインポートして名前をrdとする from matplotlib import animation,rc # @アニメーションのモジュールをインポートする（Google Colab用） # A%matplotlib nbaggはアニメーション機能の開始（Jupyter 用。Google Colabでは@行必併用。コメント分不可） %matplotlib nbagg rc('animation',html='jshtml') # Bアニメーションをjavascriptで実行する設定 import matplotlib.pyplot as plt # Cグラフを使うライブラリ　名前をpltにします fig = plt.figure() # Dグラフの描画領域の設定 ims=[] # Eグラフのイメージ（画像）のリスト定義 #選択ソートの関数 def selectionsort(data): # 並び替え前のランダムなデータリストを受け取る for i in range(0,len(data),1): # iは０からリスト数−１まで１ずつ増える for j in range(i+1,len(data),1): # jはi＋１からリスト数−１ま１ずつ増える if data[i]を<に変更 temp = data[i] # 入れ替え処理 data[i] = data[j] # data[j] = temp # im = plt.bar(b,data,color="orange") # F棒グラフを描画してイメージをimに入れる ims.append(im) # Gイメージimをイメージリストimsに追加していく #メインプログラム data_list = [] #データリストの定義 data_list = rd.randint(1,100,100) #１から１００の整数を１００個作りdata_listに入れる b=range(len(data_list)) # HグラフのX軸用に、データリストの要素数分のリストを作る #ソート前 print(" ソート前（先頭10個のデータ）",data_list[0:10])#ソート前データ、データ数が多いので先頭１０個だけ表示 selectionsort(data_list) # ソート実行 print(" ソート後（先頭10個のデータ）",data_list[0:10])#ソート後データ、データ数が多いので先頭１０個だけ表示 anim = animation.ArtistAnimation(fig,ims,interval=100)#Iグラフのイメージを表示エリアに100ms間隔で表示する設定 anim #Jグラフのアニメーションを表示 ３　交換ソート（bubble sort） 課題3-1 (1) # 交換ソート（降順） #プログラム中の@〜Jはアニメーション用のプログラムです #アニメーション表示なしで高速に実行するためには@〜J（最小でF〜J）をコメント文にしてください。 import numpy.random as rd # numpy.randomモジュールをインポートして名前をrdとする from matplotlib import animation,rc # @アニメーションのモジュールをインポートする（Google Colab用） # A%matplotlib nbaggはアニメーション機能の開始（Jupyter 用。Google Colabでは@行必併用。コメント分不可） %matplotlib nbagg rc('animation',html='jshtml') # Bアニメーションをjavascriptで実行する設定 import matplotlib.pyplot as plt # Cグラフを使うライブラリ　名前をpltにします fig = plt.figure() # Dグラフの描画領域の設定 ims=[] # Eグラフのイメージ（画像）のリスト定義 # 交換ソートの関数 def bubblesort(data): for i in range(len(data)): # iは０からリスト数−１まで１ずつ増える for j in range(len(data)-i-1): # jは０からリスト数−１から１づつ減る数まで増える if data[j] < data[j+1]: # 隣（グラフでは右）のデータと比較して小さければ入れ替える****>を<に変 temp = data[j] # 入れ替え処理 data[j] = data[j+1] # jの繰り返しで一番大きいデータがうしろ（グラフでは右）に置かれる data[j+1] = temp # im = plt.bar(b,data,color="lightgreen") # F棒グラフを描画してイメージをimに入れる ims.append(im) # Gイメージimをイメージリストimsに追加していく data_list = [] # リストの定義 data_list = rd.randint(1,100,100) #１から１００の整数を１００個作りdata_listに入れる b=range(len(data_list)) # HグラフのX軸用に、データリストの要素数分のリストを作る print(" ソート前（先頭10個のデータ）",data_list[0:10]) bubblesort(data_list) # ソート実行 print(" ソート後（先頭10個のデータ）",data_list[0:10]) anim = animation.ArtistAnimation(fig,ims,interval=100) # Iグラフのイメージを表示エリアに100ms間隔で表示する設定 anim # Jグラフのアニメーションを表示 ４　クイックソート（quick sort） 課題4-1 (1) # クイックソート(降順) #プログラム中の@〜Jはアニメーション用のプログラムです #アニメーション表示なしで高速に実行するためには@〜J（最小でF〜J）をコメント文にしてください。 import numpy.random as rd # numpy.randomモジュールをインポートして名前をrdとする from matplotlib import animation,rc # @アニメーションのモジュールをインポートする（Google Colab用） # A%matplotlib nbaggはアニメーション機能の開始（Jupyter 用。Google Colabでは@行必併用。コメント分不可） %matplotlib nbagg rc('animation',html='jshtml') # Bアニメーションをjavascriptで実行する設定 import matplotlib.pyplot as plt # Cグラフを使うライブラリ　名前をpltにします fig = plt.figure() # Dグラフの描画領域の設定 ims=[] # Eグラフのイメージ（画像）のリスト定義 #クイックソートの関数 def quick_sort(data,left, right): #引数はデータリスト、左開始点、右開始点 i = left # 左の開始点のインデックス（データ位置） j = right # 右の開始点のインデックス（データ位置） pivot =data[ (left + right) // 2]# 左右の中心位置のデータ（ピボット）を求める(//は商の演算) # ソート対象のインデックスを探索 while True: while data[i] > pivot: #ピボットよりデータが大きかったら（正しい順）****<を>に変える i = i + 1 #探索するデータを右にずらす while data[j] < pivot: #ピボットよりデータが小さかったら（正しい順）****>を<に変える j = j - 1 #探索するデータを左にずらす # 無限ループ終了条件 if i >= j: #探索する位置が右と左が同じか、左が右を超えたら終わり break #関数の終わり # ピボットの両側にあるデータを交換 tmp = data[i] #tmpを介した交換 data[i] = data[j] # data[j] = tmp # # 範囲を一つ狭める i = i + 1 #交換が終わったので左の開始点を増やす j = j - 1 #交換が終わったので右の開始点を減らす im = plt.bar(b,data,color="violet") #F棒グラフを描画してイメージをimに入れる ims.append(im) #Gイメージimをイメージリストimsに追加していく # 再帰処理　交換の範囲を現在のピボットの左側または右側に設定して再度ソート関数に渡す if left < i - 1: #左開始点より探索位置が大きかったら（まだソートできていない） quick_sort(data,left, i - 1) #左開始点からピボット位置手前までをソート if right > j + 1: #右開始点より探索位置が小さかったら（まだソートできていない） quick_sort(data,j + 1, right)#右開始点からピボット位置手前までをソート data = [] # リストの定義 data = rd.randint(1,100,100) #１から１００の整数を１００個作りdata_listに入れる b=range(len(data)) #HグラフのX軸用に、データリストの要素数分のリストを作る print(" ソート前（先頭10個のデータ）",data[0:10]) quick_sort(data,0,len(data)-1) # ソート実行 print(" ソート後（先頭10個のデータ）",data[0:10]) anim = animation.ArtistAnimation(fig,ims,interval=100)#Iグラフのイメージを表示エリアに100ms間隔で表示する設定 anim #Jグラフのアニメーションを表示 ５　ヒープソート（Heap sort） 課題5-1 リスト（配列）の番号とヒープの関係は次の図です。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 (1)親の番号から子の番号を求める リスト（配列）番号を親の番号として式 　child = 2 * parent + 1　 に入れて計算します リスト（配列）の番号　0 1 2 3 4 5 6 7 8 9 計算結果　　　　　　　1 3 5 7 9 11 13 15 17 19 親０の子は１　　親３の子は７　になります。もう一人の子の番号は 計算結果の番号に＋１します (2)子の番号から親の番号をもとめる リスト（配列）番号を子の番号として式 parent = int((child - 1) / 2) に入れて計算します リスト（配列）の番号　0 1 2 3 4 5 6 7 8 9 計算結果　　　　　　　0 0 0 1 1 2 2 3 3 4 子１子２の親は０　子７子８の親は３になります。 子０は無いので計算しないか無視します。