【第一回アルゴリズム勉強】Pythonでバブルソート + クイックソート🐩🐕🐕‍🦺

アルゴリズム勉強会を始めた💓

今回はクイックソートについて学び開発仲間に複数のソートを教えたので、簡単にソースコードを貼っていこうと思う。

環境

• Python3🐍

• AOJで開発勉強メンバの理解を確認(AtCoderでいい感じのイージー問題を見つけれかったためAOJ)✒️✒️✒️

バブルソート🔵🔵🔵

すごい簡単なので簡易的にソートを行いときに良く使っていますw。(Goのバージョンが低い時とか？)

参考

バブルソート : アルゴリズム

AOJ

タイトル未設定

コード

# def bubble_sort(array: list):
#     for i in range(len(array)):
#         for j in range(0, len(array) - i - 1):
#             if array[j] > array[j + 1]:
#                 array = swap(array, j, j + 1)


def swap(array: list, a: int, b: int):
    array[a], array[b] = array[b], array[a]
    return array


def count_bubble_sort_swap(array: list):
    result = 0
    for i in range(len(array)):
        for j in range(0, len(array) - i - 1):
            if array[j] > array[j + 1]:
                array = swap(array, j, j + 1)
                result += 1

    return result


while True:
    n = int(input())
    if n == 0:
        break
    arr = []
    for i in range(n):
        arr.append(int(input()))

    print(count_bubble_sort_swap(arr))

クイックソート🌪🌪🌪🌪🌪🌪

適当なところを探すのは辛いと思いますが、ある程度探索対象量が多い時に使うイメージ

参考

クイックソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）

AOJ

タイトル未設定

コード

import copy


def swap(arr: list, i, j: int) -> list:
    arr[i], arr[j] = arr[j], arr[i]
    return arr


def partition(arr: list, start, end: int, listGetter) -> (list, int):
    pivot = listGetter(arr, end)
    p = start
    for i in range(start, end):
        if listGetter(arr, i) <= pivot:
            swap(arr, p, i)
            p += 1

    return swap(arr, p, end), p


def quick_sort(arr: list, start, end: int, listGetter):
    if start < end:
        # print(arr, start, end, ":", arr[start:end + 1], end="->")
        _, p = partition(arr, start, end, listGetter)
        # print(arr[start:end + 1], "left:", arr[start:p], "right:", arr[p + 1:end + 1], p)
        quick_sort(arr, start, p - 1, listGetter)
        quick_sort(arr, p + 1, end, listGetter)
    return arr


class Value:
    value: int
    key: str

    def __init__(self, value: int, key: str):
        self.value = value
        self.key = key


if __name__ == '__main__':
    arr = []
    n = int(input())

    for i in range(n):
        kv = input().split(" ")
        arr.append(Value(key=kv[0], value=int(kv[1])))

    stabled = sorted(copy.deepcopy(arr), key=lambda x: x.value)
    quick_sort(arr, 0, len(arr) - 1, lambda a, i: a[i].value)

    isStable = True
    for i, v in enumerate(stabled):
        if arr[i].key != v.key or arr[i].value != v.value:
            isStable = False
            break

    print("Stable" if isStable else "Not stable")
    for v in arr:
        print(v.key, v.value)

GitHub

GitHub - DolkMd/training-algorithm-1