いろんなアルゴリズム"00.00.00.07"

立ち位置・仕様

• いろんなアルゴリズムをコピペできるように記録するのみ
• 最適化が目的でない
• たまにメモとして解説を残す
• 最低限でまとめる
• データを抽出しやすいように個別のIDを付与
• あるアルゴリズムにおいて、他のアルゴリズムが登場する際にはそのIDを付与
• IDは16進数表記
• なるべく最低限なパッケージで実装
• なるべく特殊なオブジェクト型は使用しない

TargetID

00.00.00.07

ReferenceID

マージソート

def mergeSort(l):
    if len(l) <= 1:
        return l

    mid = len(l) // 2
    left = l[:mid]
    right = l[mid:]

    left = mergeSort(left)
    right = mergeSort(right)

    return merge(left, right)

def merge(left, right):
    merged = []
    left_i, right_i = 0, 0

    while left_i < len(left) and right_i < len(right):
        if left[left_i] <= right[right_i]:
            merged.append(left[left_i])
            left_i += 1
        else:
            merged.append(right[right_i])
            right_i += 1

    if left_i < len(left):
        merged.extend(left[left_i:])
    if right_i < len(right):
        merged.extend(right[right_i:])

    return merged

使用方法

l = [5,2,3,6,2,1]
l = mergeSort(l):
print(l) # [1, 2, 2, 3, 5, 6]