自分で記事を書いたら暗記できるだろうと思い、こちらに残します。
その他ソートについて随時追加していきます。
wikipediaに掲載されているソートタイプを全て網羅するつもりですので気になる方はストックいただけたら幸いです。
wiki全ソート中現在 12/22 掲載中
今後各ソートの処理時間の比較なども追加していく予定です。
全て引数をarr(arrayの略)としています。
またわかりやすよう全て昇順に並び替えるのを目的のコードを作成しています。
目次
ー以下各種ソート(重要だと思うもの)ー
・選択ソート
・挿入ソート
・シェルソート
・バブルソート
・シェーカーソート
・コムソート
・ノームソート
・マージソート
・クイックソート
・バケットソート
-各種ソート(あまり重要ではない)-
・ボゴソート
・基数ソート
それではみていきましょう。
ここでは
・特徴など一言
・コード
・計算量
の順に述べていきます。
計算量について
これがとても大事です。
お買い物に行く前にどのくらいお金を持って行くか決めるようなのものです。これを知らないのは100円を握りしめてPS5を買いに行くのと同じです。
主に時間計算量と領域計算量に分かれます。
・時間計算量：プログラム実行時の計算にかかる時間
・領域計算量：プログラム実行時に必要なメモリ内の記憶領域
このような認識でいいかと思います。
用いるコンピュータの性能などの外的要因により変動するため、O表記法によって表現されます。
詳しい説明は避けますので気になる方は検索して見てください。
またまとめれる機会があればまとめます。
実行時間の測定
Pythonのtimeitモジュールを用います。
import timeit
timeit.timeit("測定したい関数名等", globals=globals(), number=1)
#引数globalsにglobals()を渡すことで、グローバルな名前空間でコードが実行される。
#numberは繰り返し回数
それでは具体的なアルゴリズムを確認していきましょう。
選択ソート
イメージフロー
①先頭を除くリストから最小のものを選ぶ
②先頭のものと交換する
を繰り返すことで並び替えをおこなうアルゴリズムです。個人的には一番イメージしやすいかなと思います。
計算量
計算量は $ O(n^2) $
特徴
不安定なソートと言われます。(安定なソートはこちらを参照)
#選択ソート
def select_sort(arr):
for i in range(0,len(arr)-1):
min=i
for j in range(i, len(arr)):
if arr[min]>arr[j]:
min=j
arr[min],arr[i]=arr[i],arr[min]
挿入ソート
「前半にソート済みの新しいリストを作って行く」イメージです。
イメージフロー
①リストの2個目の要素を一つ前の要素と比較
②もしリストの１番目の要素の方が大きいなら並び替え
を繰り返します。
計算量
計算量は $ O(n^2) $
特徴
データの内容によって計算量が大きく変動。
新しく作った要素に入る要素が常に先頭に行く場合が最悪のケースとなります。
逆にすでにソート済みな配列に対しては計算量は$ O(n) $ となります。
#挿入ソート
def insert_sort(arr):
for i in range(1,len(arr)):
tem=arr[i]
for j in range(i-1,-1,-1):
if tem>arr[j] or tem==arr[j]:
arr[j+1]=tem
break
elif tem<arr[j]:
arr[j+1]=arr[j]
else:
arr[0]=tem
シェルソート
挿入ソートを改良したものです。
間隔を開けたものに対してソートを行い、だんだんその間隔を小さくしていくことでソートを行います。
個人的には作り方が下で紹介しているコムソートとも類似している気がします。
イメージフロー
①リストの要素を特定間隔前のの要素と比較
②ソート
③徐々に間隔を小さくしていく
シェルソートという名前も他のソートの名前と同様に「貝殻のようだから」かと思いましたがシェルさんが開発したものだから、らしいです笑
計算量
計算量は $ O(n^2) $
特徴
もっとも相性のいいリストに対しては計算量は $ O(nlog(n)) $となります。
また安定でないソートです。
#シェルソート
#このコードではリストの数を2で割ることで最初の間隔を定めています。
def shell_sort(arr):
# 間隔gap
gap=len(arr)//2
while gap >0: #gapが0になれば終了(1//2=0)
for i in range(len(arr)-gap):
while i==0 or i-gap >= 0: #i-gapが0以下になるまで繰り返し処理
tem=arr[i+gap]
if tem<arr[i]:
arr[i+gap],arr[i]=arr[i],arr[i+gap]
i-=gap
gap=gap//2
return arr
print(shell_sort(numbers))
バブルソート
イメージフロー
①リストの最後から隣どうしを比較
②もし前の要素が大きいならそれぞれを入れ替え
を繰り返します。
水の中の泡のように徐々に上に浮いて行く様子からバブルソートとつけれらたそうです。
計算量
こちらも計算量は $ O(n^2) $ です。
#バブルソート
def bubble_arr(arr):
for i in range(0,len(arr)-1):
for j in range(len(arr)-1, i,-1):
if arr[j]<arr[j-1]:
arr[j],arr[j-1]=arr[j-1],arr[j]
シェーカーソート
イメージフロー
バブルソートの改良版です。
バブルソートではスキャンを一方向にしか行わなかったのに対し、シェーカーソートでは交互に二方向に行います。
カクテルソートとも呼ばれます。
カクテルを降る時みたいな動きになるためこの名前がついたそうです。
計算量
こちらも計算量は $ O(n^2) $ です。
#カクテルソート
def cocktail(arr):
flag=True #flagにてソート完了を認識
start=0
end=len(arr)-1
while flag:
flag=False
for i in range(start,end):
if arr[i]>arr[i+1]:
arr[i+1],arr[i]=arr[i],arr[i+1]
flag=True
if not flag:
break
end -=1
for j in range(end-1, start-1, -1):
if arr[j]>arr[j+1]:
arr[j+1],arr[j]=arr[j],arr[j+1]
flag=True
start -=1
return arr
print(cocktail(numbers))
コムソート
イメージフロー
こちらもバブルソートの改良版です。
バブルソートでは隣接している要素同士に対してを繰り返し処理を行ったいた一方こちらは数個飛ばして要素の判別を行います。
くし(comb)みたいに間が空いていることからこの名前がついたそうです。
計算量
こちらも計算量は $ O(n^2) $ です。
ただしもっとも処理が早く行った場合、前述のバブルソート、シェーカーソートでは$ O(n) $ だったのに対してこちらのコムソートでは$ O(nlog(n)) $となります。
さらに安定したソートではないです。
#コムソート
#gapが１でない間回す
def comb(arr: List[int]) -> List[int]:
gap=len(arr)
flag=True
while gap !=1 or flag:
gap=int(gap//1.3)
if gap<1:
gap= 1
flag= False
for i in range(0, len(arr)-gap):
if arr[i]>arr[i+gap]:
arr[i],arr[i+gap]=arr[i+gap],arr[i]
flag=True
return arr
print(comb(numbers))
ノームソート
イメージフロー
バブルソートのような動きをします。
隣接する要素を比較し並びが違う場合、入れ替え(ここまではバブルソートと同じ)し、その後一つ前に戻ります。
これを繰り返すことでソートしていきます。
オランダのノームが一列に並んだ鉢植えの花をソートする話が由来らしいです。
計算量
こちらも計算量は $ O(n^2) $ です。
特徴
下のコードを見るとわかるのだが入れ子のループを用いない単純な構造の上に挿入ソートと同程度の性質を有する。
また処理対象全部を読み込む前にソートを開始できるため、標準入力やパイプラインで読み込みながら並行してソート処理が行えるという特徴もある。
#ノームソート
def gnome_sort(arr):
index=0
while index<len(arr):
if index==0:
index+= 1
#並び替えが不要な場合
if arr[index] >= arr[index-1]:
index+= 1
#並び替えが必要な場合→前に戻る
else:
arr[index],arr[index-1]=arr[index-1],arr[index]
index-= 1
return arr
print(gnome_sort(numbers))
マージソート
分割統治法を用います(詳しい説明はこちら(引用サイト))。
受け取ったリストを分割して再集合することでソートを行います。
イメージフロー
①リストを要素が１つになるまで全てバラバラに
②リストどうしを比較→並び替え(ソート)
一回分割する、余計なことしてるやんと思うかもしれないですが計算量を求めると確かに効率の良いものになってます。
計算量
こちらは計算量は $ O(nlogn) $ です。
参考としてそれぞれのグラフも作成しましたのでこちらで確認ができるかと思います。(x=10でこれだけ違う！)
#マージソート
def merge_sort(arr):
if len(arr)<2:
return arr
mid=len(arr)//2
return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))
def merge(arrf,arrb):
if len(arrf)<1:
return arrb
elif len(arrb)<1:
return arrf
if arrf[0]<=arrb[0]:
return [arrf[0]]+merge(arrf[1:],arrb)
else:
return [arrb[0]]+merge(arrf, arrb[1:])
クイックソート
こちらも分割統治法を用いた手法です。
感覚的にマージソートよりもイメージしやすいです。
イメージフロー
①要素のうち一つを選ぶ(pとする)
②残りの要素を「pより小さい」「pと同じ」に分類し、それぞれ別々のリストに格納する。
③前半、後半の部分配列に対して再びソートを行う。
を繰り返します。
計算量
こちらは計算量は $ O(nlogn) $ です。
特徴
「すでにソート済みの配列に対してソートする場合」
この場合、毎回の左右分割において常に片方に偏ってしまうため、計算量は$ O(n^2) $となってしまいます。
この場合、最初に決定するp(ピボット)をランダムに取得することで解決ができます。
#クイックソート
def quick_sort(arr):
if len(arr)<2:
return arr
p=arr[0]
arrf,arrb= divide(p, arr[1:])
return quick_sort(arrf)+ [p] + quick_sort(arrb)
def divide(p, arr):
left,right=[],[]
for i in arr:
if i<p:
left.append(i)
else:
right.append(i)
return left,right
バケットソート
イメージ
特定の数字を特定の場所にいれておけるようにするバケットというカゴのようなリストを用意しておき、そこからソートをしていく方法です。言葉ではイメージがつかみにくいためコードをみてください。
計算量
こちらは計算量は $ O(n) $ です。
え、これ一番いいじゃんと思った方が多いと思いますがこれには制限が多くあります。(特徴にて)
特徴
計算量からわかるように要素数に比例するだけの大変優れたアルゴリズムなのですが以下の点に注意です。
・データの値の範囲が有限個の整数で表現できなければならない。(リストの要素数の限界)
・データの値の種類の分だけリスト要素を用意する必要があるため、メモリを浪費してしまう可能性がある。
また受け取るリスト内要素が整数でないといけません。
改良
→一つのバケットに複数の数値を入れるようにする(10こ単位など)
１つのバケットに１つの数字のみを入れるものをカウントソートと呼ぶことがあります。
諸刃の剣的な感じですね。グッドなタイミングで出せたらいいですね。
#バケットソート
def backet_sort(arr):
counter=[0*i for i in range(0,len(arr))]
for j in arr:
counter[j]+=1
c_counter=cumulative_sum(counter)
new_arr=[0]*len(arr)
for h in reversed(arr):
new_arr[c_counter[h]-1]+=h
c_counter[h]-=1
return new_arr
def cumulative_sum(arr):
for i in range(1,len(arr)):
arr[i]+=arr[i-1]
return arr
---以下参考がてら--
ボゴソート
イメージ
うまく並べるまでとにかくランダムに並び替える脳筋なソートです。
実用性はありません(多分)。
計算量
こちらは計算量は $ O((n+1)!) $ です。
ランダムなので早かったり遅かったりします。
#ボゴソート
def bogo(arr):
while not inOrder(arr): #arrがTrue出ないと繰り返し処理
random.shuffle(arr)
return arr
def inOrder(arr): #ランダムに並べたリストが昇順になってるか調べる関数
for i in range(len(arr)-1):
if arr[i]>arr[i+1]:
return False
return True
#一行でこうやって書くこともできる
#return all(arr[i]>=arr[i+1] for i in range(len(arr)-1))
#ここまで
nums=[random.randint(0,1000) for _ in range(10)]
bogo(nums)
print(nums)
基数ソート
バケットソートを使用したソートアルゴリズムです。
コード自体が長くなるため、どないやろと思いました。
イメージ
バケットソートの分類をさらに複数に分けて行います。
①1の位でのバケットソート→処理後はそのまま繋げてリストにする
②10の位でのバケットソート→処理後は同様
・・・
を繰り返す。
計算量
こちらはバケットソートと同様計算量は $ O(n) $ です。
特徴
バケットソートと同様に最初に最大値文のリストを作成するため
・整数値の処理
・最大値が小さい
などの制限があります。
#ソート
def counting_sort_digit(arr, digit): #こちらでバケットソートを処理→リストをリターン
result_arr = [0 for _ in arr]
counting_arr = [0 for _ in range(0, 10)]
for i in range(len(arr)):
index = arr[i] // digit
counting_arr[index % 10] += 1
for i in range(1, 10):
counting_arr[i] += counting_arr[i-1]
for j in range(len(arr)-1, -1, -1):
index = arr[j] // digit
result_arr[counting_arr[index % 10]-1] = arr[j]
counting_arr[index % 10] -= 1
return result_arr
def radix_sort(arr, radix):
max_num = max(arr)
digit = 1
while max_num // digit > 0:
array = counting_sort_digit(arr, digit)
digit *= radix
return arr
最後に
これからも随時追加していきますのでよろしければストックください。
頑張って覚えよう。データ構造も後日まとめる。(決意)
参考文献
・wikipedia(templateアルゴリズム)
(url:https://ja.wikipedia.org/wiki/Template:%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0)
・ノームソートとは
(url:https://goo.to/word/686315389)