以前の面接のコーディング試験で配列ソートの課題がでました。 競技プログラミングで何度もソートはしたものの標準ライブラリで行っていたため、実際のアルゴリズムは分かっていませんでした。

なので今回は基本的な3つのソートについて Python で実装してみました。

バブルソート

配列の一番左の値を取ってきて右隣のものと比較し、右隣の方が小さければ交換します。 この作業を配列の長さ分行えば、全てソートされるので計算量は O(n^2)かかります。

Pythonでの実装例

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

# example
A = [2,3,4,1,5]
sorted_A = bubble_sort(A) # [1,2,3,4,5]

挿入ソート

ソート済みの区間に対して未ソート区間から数を差し込んでいきます。

Pythonでの実装例

def insertion_sort(A):
    n = len(A)
    # i:未ソートの先頭のindex
    for i in range(n):
        # v:未ソートの先頭の配列の数
        v = A[i]
        # j:ソート済みの配列からvを差し込む位置を探すループ変数
        j = i - 1
        while j >= 0 and A[j] > v:
            A[j+1] = A[j]
            j -= 1
            A[j+1] = v
    return A

選択ソート

それぞれの区間から最小値を見つけて順番に交換していくソートです。割と直感的なアルゴリズムで分かりやすいです。

Pythonでの実装例

n = int(input())
A = list(map(int, input().split()))
cnt = 0
def selection_sort(A):
    n = len(A)
    for i in range(n):
        min_j = i
        for j in range(i, n):
            if A[j] < A[min_j]:
                min_j = j
            if i != min_j:
                A[i], A[min_j] = A[min_j], A[i]
    return A

他にもクイックソートやシェルソートなどのたくさん種類があるらしいです。 ソートはアルゴリズムのらしいので、しっかり実装できるようにしたいです。