ソートアルゴリズム覚書き by Python

ソートのアルゴリズムについては、名前は色々知っているのですが、書こうと思って空で書けるのは挿入ソートくらいだったりします。

そんな各種のソートについてPythonでの書き方をまとめます。
・挿入ソート
・マージソート
・クイックソート
・ヒープソート
・バケットソート

挿入ソート

左からi番目までを小さい順に並べ替えて行き、i+1番以降も同様に最後のN番目に到るまで並べ替えを繰り返すアルゴリズムです。

InsertionSort.py

# 挿入ソート
# 計算量：O(N^2)
def InsertionSort(a):
    for i in range(len(a)):
        v = a[i]

        j = i
        while j > 0:
            if a[j-1] > v:
                a[j] = a[j-1]
            else:
                break
            j -= 1
        a[j] = v
    return a

a = list(map(int, input().split()))

InsertionSort(a)

# 入力
# 2 4 3 7 5 6 1

# 出力
# [1, 2, 3, 4, 5, 6, 7]

マージソート

配列を再帰的に半分のサイズに分割して行き、最小サイズに至ったら今度は分割した配列同士を比較して小さい順に値を並べ替え、それらを再帰的に結合して最終的に元の配列を並べ替える分割統治法を活用したアルゴリズムです。

MergeSort.py

# マージソート
# 計算量　：O(NlogN)
def MergeSort(a, left, right):
    if (right-left) == 1:
        return a
    mid = left + (right-left)//2

    a = MergeSort(a, left, mid)
    a = MergeSort(a, mid, right)

    buf = []
    for i in range(left, mid):
        buf.append(a[i])
    for i in range(right-1, mid-1, -1):
        buf.append(a[i])

    index_left = 0
    index_right = len(buf)-1
    for i in range(left, right):
        if buf[index_left] <= buf[index_right]:
            a[i] = buf[index_left]
            index_left += 1
        else:
            a[i] = buf[index_right]
            index_right -= 1

    return a

a = list(map(int, input().split()))

MergeSort(a, 0, len(a))

# 入力
# 2 4 3 7 5 6 1

# 出力
# [1, 2, 3, 4, 5, 6, 7]

クイックソート

適当な要素をpivotとして選び、配列全体をpivot以上とpivot以下のグループに分割し、それぞれのグループで再帰的に同じことを繰り返して、最終的に元の配列を並べ替える分割統治法を活用したアルゴリズムです。

QuickSort.py

# クイックソート
# 計算量：O(N^2)
def QuickSort(a, left, right):
    if (right-left) <= 1:
        return a

    pivot_index = (left+right)//2
    pivot = a[pivot_index]
    a[pivot_index], a[right-1] = a[right-1], a[pivot_index]

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

    a[i], a[right-1] = a[right-1], a[i]

    a = QuickSort(a, left, i)
    a = QuickSort(a, i+1, right)

    return a

a = list(map(int, input().split()))

QuickSort(a, 0, len(a))

# 入力
# 2 4 3 7 5 6 1

# 出力
# [1, 2, 3, 4, 5, 6, 7]

ヒープソート

配列をヒープにした上で最大値を取り出し、残った配列を再びヒープにした上で最大値を取り出し、という処理を再帰的に繰り返して並べ替えるアルゴリズムです。

HeapSort.py

# ヒープソート
# 計算量：O(NlogN)
def HeapSort(a):
    N = len(a)

    for i in range(N//2-1, -1, -1):
        Heapify(a, i, N)

    for i in range(N-1, 0, -1):
        a[0], a[i] = a[i], a[0]
        Heapify(a, 0, i)

    return(a)

# ヒープを作成する関数
# i番目の頂点を根とする部分木について、a[0:N]の範囲をヒープ条件を満たすようにする
def Heapify(a, i, N):
    child1 = i*2+1
    if child1 >= N:
        return

    if (child1+1 < N and a[child1+1] > a[child1]):
        child1 += 1

    if (a[child1] <= a[i]):
        return

    a[i], a[child1] = a[child1], a[i]

    Heapify(a, child1, N)

a = list(map(int, input().split()))

HeapSort(a)

# 入力
# 21 35242 23132 352 3213 5321 214 2

# 出力
# [2, 21, 214, 352, 3213, 5321, 23132, 35242]

バケットソート

配列の各要素について、それ以下の値が配列の中に何個あるかをカウントし、各要素が下から何番目かに基づいて並べ替えるアルゴリズムです。

BucketSort.py

# バケットソート
# 計算量：O(N)
def BucketSort(a):
    N = len(a)
    MAX = 100000

    num = [0 for i in range(MAX)]
    for i in range(N):
        num[a[i]] += 1

    sum_ = [0 for i in range(MAX)]
    for i in range(1, MAX):
        sum_[i] = sum_[i-1] + num[i]

    a2 = [0 for i in range(N)]
    for i in range(N-1, -1, -1):
        a2[sum_[a[i]]-1] = a[i]

    return a2

a = list(map(int, input().split()))

BucketSort(a)

# 入力
# 12 42423 2314 53 342 2131 532

# 出力
# [12, 53, 342, 532, 2131, 2314, 42423]