ソートアルゴリズムの理論と実装

コーディング面接対策として、初歩的なアルゴリズムの考え方とPythonでの実装例をメモ的にまとめます。

第1回目は、ソートアルゴリズムです。ソートアルゴリズムの種類は結構ありますが、今回は下記の2つについてです。(今後追加していく可能性あり）

• バブルソート
• マージソート

アルゴリズムの理論

バブルソート

• 配列のi番目の要素に入れる値を決めるため、i+1から配列の末尾までの要素を確認していき、i+1以降で最小の値を格納したインデックスと値を入れ替える (iの初期値は0)
• 同様の処理をi = (配列の長さ - 1)まで行う
• 配列の初期状態に依存せず、たとえソートされている配列にも同様の処理を行うため、平均計算量，最悪計算量共にO(N²)となります。

マージソート

• ソートされた二つの配列をソートされた状態で連結する処理はO(N)の計算量で可能
• 配列を再帰的に半分に分割していき、一つの値からなる配列を作る (値が一つなのでソート済みである）
• 分割した配列をソート済みの状態で連結していく
• 配列を分割する回数はlogN(底は2)回であり、配列をマージする処理の計算量の合計は各層ごとにO(N)となるため、全体での計算量はO(NlogN)となる。
• 配列の初期状態に依存せず、たとえソートされている配列にも同様の処理を行うため、平均計算量，最悪計算量共にO(NlogN)となります。

Pythonで実装

import time
import random

# バブルソート
def bubble_sort(A):
    for i in range(len(A)):
        for j in range(i+1, len(A)):
            if A[i] > A[j]:
                tmp = A[i]
                A[i] = A[j]
                A[j] = tmp

    return A


# マージソート
def marge_sort(A):
    
    if len(A) == 1:
        return A

    left = marge_sort(A[:len(A)//2])
    right = marge_sort(A[len(A)//2:])

    count_left = 0
    count_right = 0
    res = []
    for i in range(len(left) + len(right)):
        if count_left == len(left):
            res.append(right[count_right])
            count_right += 1
            
        elif count_right == len(right):
            res.append(left[count_left])
            count_left += 1

        elif left[count_left] > right[count_right]:
            res.append(right[count_right])
            count_right += 1

        else:
            res.append(left[count_left])
            count_left += 1

    return res


if __name__ == '__main__':
    a = [random.randint(1, 1000) for _ in range(1000)]
    s = time.time()
    b = bubble_sort(a)
    print(time.time() - s)

    a = [random.randint(1, 1000) for _ in range(1000)]
    s = time.time()
    b = marge_sort(a)
    print(time.time() - s)

実行結果は下記の通りになりました。

0.03351020812988281
0.0031762123107910156