Python学習シート(ソートアルゴリズム編) 2 選択ソート(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は0からリスト数−1まで1ずつ増える for j in range(i+1,len(data),1): # jはi+1からリスト数−1ま1ずつ増える 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) #1から100の整数を100個作りdata_listに入れる b=range(len(data_list)) # HグラフのX軸用に、データリストの要素数分のリストを作る #ソート前 print(" ソート前(先頭10個のデータ)",data_list[0:10])#ソート前データ、データ数が多いので先頭10個だけ表示 selectionsort(data_list) # ソート実行 print(" ソート後(先頭10個のデータ)",data_list[0:10])#ソート後データ、データ数が多いので先頭10個だけ表示 anim = animation.ArtistAnimation(fig,ims,interval=100)#Iグラフのイメージを表示エリアに100ms間隔で表示する設定 anim #Jグラフのアニメーションを表示 3 交換ソート(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は0からリスト数−1まで1ずつ増える for j in range(len(data)-i-1): # jは0からリスト数−1から1づつ減る数まで増える 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) #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グラフのアニメーションを表示 4 クイックソート(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) #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グラフのアニメーションを表示 5 ヒープソート(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 親0の子は1  親3の子は7 になります。もう一人の子の番号は 計算結果の番号に+1します (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 子1子2の親は0 子7子8の親は3になります。 子0は無いので計算しないか無視します。