Python学習シート（ソートアルゴリズム編） ２　選択ソート（select sort） #選択ソート #プログラム中の@〜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]>data[j]: # data[i]とdata[j]を比べdata[j]が小さければ入れ替える 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） # 交換ソート #プログラム中の@〜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） # クイックソート #プログラム中の@〜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） #プログラム中の@〜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 heap_sort(data):#引数はデータリスト i = 0 #開始位置 n = len(data) #終了位置（データの数） #ヒープの構成 while(i < n):#開始位置が終了位置より小さいとき upheap(data, i)#[i]を親としたピープを構成する関数へ i += 1 #開始位置を一つ増やします while(i > 1):# 最終位置から先頭の前まで繰り返し i -= 1 # data[0] , data[i] = data[i] , data[0]#[0]の最大値と[i]を交換 # ヒープの再構成 downheap(data, i-1)#ダウン関数へ im = plt.bar(b,data,color="salmon") #F棒グラフを描画してイメージをimに入れる ims.append(im) #Gイメージimをイメージリストimsに追加していく # ルート[0]をヒープ(0〜n)の最適な位置へ移動 def downheap(data, n):# if n==0: return#終了位置が０なら戻る parent = 0#親を０番とする while True:# child = 2 * parent + 1 # data[n]の子要素（親の右となり） if child > n:# 要素外へ出るとbrake（子供の位置が終了点より大きい） break if (child < n) and data[child] < data[child + 1]:# 隣の子がいてかつ 左＜右 なら右の子を見る child += 1 if data[parent] < data[child]:# 親が子より小さい場合 data[child] , data[parent] = data[parent] , data[child]#親子を入れ替え parent = child; # 交換後のインデックスを保持 else: break #ヒープを構成する関数 def upheap(data, n): while n: parent = int((n - 1) / 2)#位置nの親位置を計算する if data[parent] < data[n]:#もし親が子より小さかったら data[n] , data[parent] = data[parent] , data[n]#入れ替え n = parent else: break data_list = [] # リストの定義 data_list = rd.randint(1,100,100)#１から１００の整数を１００個作りdata_listに入れる b=range(len(data_list)) #HグラフのX軸用に、データリストの要素数分のリストを作る(初期表示） im = plt.bar(b,data_list,color="salmon") #F棒グラフを描画してイメージをimに入れる（初期表示） ims.append(im) #Gイメージimをイメージリストimsに追加していく print(" ソート前（先頭10個のデータ）",data_list[0:10]) heap_sort(data_list) # ソート実行 print(" ソート後（先頭10個のデータ）",data_list[0:10]) anim = animation.ArtistAnimation(fig,ims,interval=100)#Iグラフのイメージを表示エリアに100ms間隔で表示する設定 anim#Jグラフのアニメーションを表示