Python学習シート(ソートアルゴリズム編) 2 選択ソート(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は0からリスト数−1まで1ずつ増える for j in range(i+1,len(data),1): # jはi+1からリスト数−1ま1ずつ増える 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) #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) # 交換ソート #プログラム中の@〜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) # クイックソート #プログラム中の@〜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) #プログラム中の@〜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#終了位置が0なら戻る parent = 0#親を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)#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グラフのアニメーションを表示