Edited at

Pythonで基本的なソート

More than 1 year has passed since last update.

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)