Python sorting外観

前3回ほど、pythonのlist操作についての記事を書きましたが、
Python コーディング(基) list編 - サブロウ丸
Pythonコーディング(注) list編 - サブロウ丸
Python コーディング(豆) list編 - サブロウ丸
その応用として、 みなさんお馴染みのsortingをコーディングしてみました。
cやjavaよりも簡単にかけます、そう、Pythonならね。好き。
(ちなみに、全て昇順になるようにsortしています)
そもそもpythonにはsort()関数があるよね?　というツッコミはナシです。

バブルソート

def bubble_sort(a):
    n = len(a)
    for i in range(n-1):
        for j in range(n-i-1):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
    return a

選択ソート

def select_sort(a):
    n = len(a)
    for i in range(n):
        key = a[i:].index(min(a[i:])) 
        a[i], a[i+key] = a[i+key], a[i]
    return a

ちなみにkey = a[i:].index(min(a[i:]))のところは
numpyモジュールを使ったほうが個人的には直感的に分かりやすいです。

import numpy as np
def select_sort(a):
    n = len(a)
    for i in range(n):
        key = np.argmin(a[i:])   #ここを変更 
        a[i], a[i+key] = a[i+key], a[i]
    return a

挿入ソート

def insert_sort(a):
    for i, key in enumerate(a):
        j = i - 1
        while j >= 0 and a[j] > key:
            j = j - 1
        a.insert(j+1, a.pop(i))
    return a

クイックソート

# 再帰
def quick_sort(seq):
    if len(seq) < 2:
        return seq
    pivot = seq.pop()
    left_seq = [x for x in seq if x < pivot]
    right_seq = [x for x in seq if x >= pivot]
    return quick_sort(left_seq) + [pivot] + quick_sort(right_seq)

# 再帰なし
def quick_sort2(a):
    que = [ (0, len(a)-1) ]
    while len(que) != 0:
        left, right = que.pop(0)
        if left < right:
            pivot = a.pop(right)
            left_seq = [x for x in a[left:right] if x < pivot]
            right_seq = [x for x in a[left:right] if x >= pivot]
            a[left:right] = left_seq + [pivot] + right_seq
            if len(left_seq) > 1:
                que.append( (left, left+len(left_seq)-1) )
            if len(right_seq) > 1:
                que.append( (right-len(right_seq)+1, right) )
    return a

マージソート

# 再帰
def merge_sort(seq):
    left, right = 0, len(seq)-1
    if left >= right:
        return seq
    k = (left+right)//2
    L = merge_sort(seq[left:k+1]) + [float('inf')]
    R = merge_sort(seq[k+1:right+1]) + [float('inf')]
    p, q = 0, 0
    while  p+q < right-left+1:
        if L[p] < R[q]: seq[left + (p+q)] = L[p]; p = p + 1
        else: seq[left + (p+q)] = R[q]; q = q + 1
    return seq

#　再帰なし
def merge_sort2(a):
    stack, head, tail = [(0, len(a)-1)], 0, 1
    while head < tail:
        left, right = stack[head]
        if left < right:
            k = (left+right)//2
            stack.append( (left, k) )
            stack.append( (k+1, right) )
            tail = tail + 2
        head = head + 1
    while len(stack) != 0:
        left, right = stack.pop()
        k = (left+right)//2
        if left < right:
            L = a[left:k+1] + [float('inf')]
            R = a[k+1:right+1] + [float('inf')]
            p, q = 0, 0
            while p+q < right-left+1:
                if L[p] < R[q]: a[left + (p+q)] = L[p]; p = p + 1
                else: a[left + (p+q)] = R[q]; q = q + 1
    return a

シェルソート

def shell_sort(a):
    n = len(a)
    gap, i, h = [], 1, 1
    while h < n:
        gap.append(h)
        h = (3**i+1)//2
        i = i + 1

    for h in gap[::-1]:
        for i in range(h, n):
            key, j = a[i], i
            while j > 0 and a[j-h] > key:
                a[j-h]= a[j]
                j = j - h
        a[j] = key
    return a

クイックソートとマージソートは再帰関数を使うと実装が楽ですが、その分メモリを食うので、再帰なしで実装するほうが現実的です。(まぁpythonだとsorted()関数で何も考えずにsortしてくれますけどね..)
個人的には再帰なしで実装する時に、使ったデータ構造(ストックとキュー)が面白いと思ったので、プログラムの説明を兼ねてまた記事を書くかもです。