Pythonとアルゴリズムの勉強のために基本的なソートを書きました。
気が向いたら今後も追加していきます。
選択ソート (selection sort)
def sSort(a):
for i in range(len(a)-1):
mi = a[i:].index(min(a[i:]))
a[i], a[i+mi] = a[i+mi], a[i]
return a
バブルソート (bubble sort)
def bSort(a):
for i in range(len(a)):
for j in range(len(a)-1, i, -1):
if a[j] < a[j-1]:
a[j], a[j-1] = a[j-1], a[j]
return a
挿入ソート (insertion sort)
def iSort(a):
for i in range(1, len(a)):
for j in range(i, 0, -1):
if a[j] >= a[j-1]:
break
else:
a[j], a[j-1] = a[j-1], a[j]
return a
クイックソート (quick sort)
def qSort(a):
if len(a) in (0, 1):
return a
p = a[-1]
l = [x for x in a[:-1] if x <= p]
r = [x for x in a[:-1] if x > p]
return qSort(l) + [p] + qSort(r)
マージソート (merge sort)
def merge(l, r):
n = len(l + r) # マージ後の配列のサイズ
s = max(l + r) + 1 # 番兵
l.append(s)
r.append(s)
a = []
while len(a) < n:
a.append(l.pop(0)) if l[0] <= r[0] else a.append(r.pop(0))
return a
def mSort(a):
if len(a) == 1:
return a
mid = len(a) // 2
l = mSort(a[:mid])
r = mSort(a[mid:])
return merge(l, r)