バブルソート、選択ソート、挿入ソート、シェルソート、マージソート、クイックソート、計数ソート（Python）

Python でソートアルゴリズムをまとめておきます。

バブルソート(Bubble Sort)

平均計算量: $O(n^2)$
最悪計算量: $O(n^2)$

bubble.py

for i in range(N-1, 0, -1):
    for j in range(i):
        if a[j] > a[j+1]:
            a[j], a[j+1] = a[j+1], a[j]

verify: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783238

選択ソート(Selection Sort)

平均計算量: $O(n^2)$
最悪計算量: $O(n^2)$

selection.py

for i in range(N):
    minj = i
    for j in range(i, N):
        if a[j] < a[minj]:
            minj = j

    a[i], a[minj] = a[minj], a[i]

verify: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783283

挿入ソート(Insertion Sort)

平均計算量: $O(n^2)$
最悪計算量: $O(n^2)$

insertion.py

for i in range(1, N):
    v = a[i]
    j = i - 1

    while j >= 0 and a[j] > v:
        a[j+1] = a[j]
        j -= 1

    a[j+1] = v

verify: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783260

シェルソート(Shell Sort)

内部で用いる挿入ソートの間隔列として、ウィキペディアの記事にあるように、$h = \frac{3^i - 1}{2}$ を満たす整数を大きい方から採用しました。

平均計算量: 間隔列として上記を採用した場合、$O(n^{1.25})$ と予想されている
最悪計算量: 間隔列として上記を採用した場合、$O(n^{1.5})$

shell.py

def insertion_sort(h):
    for i in range(h, N):
        v = a[i]
        j = i - h

        while j >= 0 and a[j] > v:
            a[j+h] = a[j]
            j -= h

        a[j+h] = v

hs = []
h = 1
while h < N+1:
    hs.append(h)
    h = 3 * h + 1

hs.reverse()

for h in hs:
    insertion_sort(h)

verify: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783355

マージソート(Merge Sort)

平均計算量: $O(n \log n)$
最悪計算量: $O(n \log n)$

merge.py

INF = 1e10  # 配列要素の取りうる最大値よりも大きく

def merge(left, mid, right):
    l = a[left:mid]
    r = a[mid:right]

    l.append(INF)
    r.append(INF)

    i = 0
    j = 0

    for k in range(left, right):
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
        else:
            a[k] = r[j]
            j += 1

def merge_sort(left, right):
    if right - left >= 2:
        mid = (left + right) // 2
        merge_sort(left, mid)
        merge_sort(mid, right)
        merge(left, mid, right)

merge_sort(0, N)

verify: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783399

クイックソート(Quick Sort)

平均計算量: $O(n \log n)$
最悪計算量: $O(n^2)$

quick.py

def partition(left, right):
    x = a[right]
    i = left-1

    for j in range(left, right):
        if a[j] <= x:
            i += 1
            a[i], a[j] = a[j], a[i]

    a[i+1], a[right] = a[right], a[i+1]
    return i+1

def quick_sort(left, right):
    if right - left >= 2:
        pivot = partition(left, right-1)
        quick_sort(left, pivot)
        quick_sort(pivot, right)

quick_sort(0, N)

verify: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783489

計数ソート(Counting Sort)

バケットソート(Bucket Sort), ビンソート(Bin Sort) の一種でもある

平均計算量: $O(n + k)$
最悪計算量: $O(n + k)$

counting.py

K = 100000 # 配列要素の取りうる種類数よりも大きく

b = [0 for i in range(len(a))]
c = [0 for i in range(K)]

for v in a:
    c[v] += 1

for i in range(K-1):
    c[i+1] += c[i]

for j in reversed(range(N)):
    b[c[a[j]]-1] = a[j]
    c[a[j]] -= 1

# b がソート済み配列

verify: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783628