アルゴリズム実装(Python) | Pyラボ(Python Lab)

Contents

はじめに
扱うソートアルゴリズム
実装
おわりに

はじめに

こんにちは、わたやんでぇす。今日はソートアルゴリズムまとめです。

僕がアルゴリズムを学ぼうと思った理由は以下の通りです。↓↓↓

日本のエンジニア採用では、志望動機やコミュニケーション力を重視される面接ですが、アメリカでは、志望動機よりもコーディングスキルが重要視されます。

Google、Apple, Facebook、Amazonの入社試験では必ずアルゴリズム、データ構造のコーディング面接が行われます。

世界をリードして最先端の技術革新をしている会社では、ちょっとでもコードが早くなるように、プログラマーが、最適なコードを書く必要があるのです。

意識の高い僕はGAFAに就職できるようなレベルには到底達していませんがアルゴリズムがわかるというのはかっこいいので学習します。

今日はソートアルゴリズムについて勉強したので代表的なソートアルゴリズムの実装したコードを載せます。

Udemyなら文章では理解が難しいアルゴリズムでも動画でわかりやすく説明されていたのでとっても役に立ちました。

Python 3 入門+アメリカのシリコンバレー流コードスタイル

扱うソートアルゴリズム

bubble sort
selection sort
merge sort

実装

bubble sort

バブルソートはリストにおいて隣り合うふたつの要素の値を比較して条件に応じた交換を行う整列アルゴリズムです。シンプルなアルゴリズムなのでデータ量が少ないのであれば手軽に実装できます。

実際のイメージ

from typing import List


def bubble_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    for i in range(len_numbers):
        for j in range(len_numbers - 1 - i):
            if numbers[j] > numbers[j + 1]:
                numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]

    return numbers

かなり短いコードでできました。実際にリストを作って値をソートしたいと思います。

ちゃんとソートできてました。

selection sort

選択ソートは配列の整列されていない部分から最小値または最大値を持つ要素を探して、その値を未整列の先頭要素に移動(交換)することを繰り返して整列を行うアルゴリズムです。

バブルソートよりも交換回数が少ないので選択ソートの方が高速になる。

from typing import List


def selection_sort(numbers: List[int]) -> List[int]:
    for i in range(len(numbers)):
        min_idx = i
        for j in range(i+1, len(numbers)):
            if numbers[min_idx] > numbers[j]:
                min_idx = j

        numbers[i], numbers[min_idx] = numbers[min_idx], numbers[i]
    return numbers

merge sort

マージソートは整列ｓだれていないリストを2つのリストに分割して、それぞれを整列させたのち、それらをマージして整列したリストを作ります。

マージとはいくつかの整列済みのリストを一つのリストにまとめる操作です。

実際のコードはこんな感じ。

from typing import List


def merge_sort(numbers: List[int]) -> List[int]:
    if len(numbers) <= 1:
        return numbers

    center = len(numbers) // 2
    left = numbers[:center]
    right = numbers[center:]

    merge_sort(left)
    merge_sort(right)

    i = j = k = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            numbers[k] = left[i]
            i += 1
        else:
            numbers[k] = right[j]
            j += 1
        k += 1

    while i < len(left):
        numbers[k] = left[i]
        i += 1
        k += 1

    while j < len(right):
        numbers[k] = right[j]
        j += 1
        k += 1

    return numbers

bubble sortやselection sortよりも長いコードになりましたが、無事書き終えることができました。

実行します。