Pythonで基本のアルゴリズムを書いてみた

アルゴリズムを学ぶ意義みたいなものはいろいろなところで語り尽くされていると思うので私からは特にコメントしませんが、今回の勉強に利用した書籍でも引用されていた言葉が印象的なので、記しておきます。

最先端の機械を使って製品をつくるのは簡単で、しかも楽なことだが、基本技術を固める前に楽なほうに流れていってしまった。俺のような基本的なことがきちんとできるローテクが、今、我が世の春を謳歌しているんだ。

岡野雅行さんという職人さんの言葉のようです。

そういえば随分前にこんな記事が盛り上がりました。
今すぐ辞めて欲しい、「Ruby on Rails勉強してます」「CakePHP勉強してます」
最新技術だけではなくて、その基礎となる技術をしっかり理解しなければダメだよということでしょう。

ということで基本のアルゴリズムを勉強して、Pythonで書いてみました。
使ったのは以下の本。基本のアルゴリズムが非常にわかりやすく解説されています。ただ、本当にアルゴリズムに絞って書かれているので、具体的なコードとかはでてこないです。その分特定の言語によらないアルゴリズムの基礎的な考え方を理解することができます。

アルゴリズムを、はじめよう

アルゴリズムを、はじめよう

以下、本で解説されているアルゴリズムを全てPythonで書いてみました。

線形探索法(リニアサーチ)

# liner.py
target = int(input())
array = [4, 2, 3, 5, 1]

def liner_search(target):
    for i in range(len(array)):
        if array[i] == target:
            return i
    print(None)

if __name__ == '__main__':
    print(liner_search(target))

二分探索法(バイナリサーチ

# binary.py
target = int(input())
array = [11, 13, 17, 19, 23, 29, 31]

def binary_search(target):
    head = 0
    tail = len(array) - 1
    while head <= tail:
        center = (head + tail) // 2
        if array[center] == target:
            return center
        else:
            if array[center] < target:
                head = center + 1
            else:
                tail = center - 1
    return None

if __name__ == '__main__':
    print(binary_search(target))

ハッシュ探索法

# hash.py
# 格納する数字の配列
arrayD = [12, 25, 36, 20, 30, 8, 42]
# ハッシュ法で数字を格納していく配列 
arrayH = [0] * 11

# データを格納する関数
def hashStore(array1, array2):
    k = 0
    for i in range(len(array1)):
        # ハッシュ値をkに代入
        k = array1[i] % 11
        # 空いてるとこがみつかるまで新たなarray2の要素を探索
        while True:
            if array2[k] == 0:
                array2[k] = array1[i]
                break
            else:
                k = (k + 1) % 11
    return array2

# データを探索する関数
def hashSearch(num, array):
    # 格納したときと同じハッシュ関数を利用
    k = num % 11
    # 要素が入っていないとこが見つかったら目的の数字は存在しない
    while array[k] != 0:
        if array[k] == num:
            return k
        else:
            k = (k + 1) % 11
    return None

if __name__ == '__main__':
    print(hashStore(arrayD, arrayH))

単純選択法(選択ソート)

# selection.py
array_to_sort = [12, 13, 11, 14, 10]

def selectionSort(array):
    for i in range(len(array) - 1):
        k = i + 1
        indexMin = i
        while k < len(array):
            if array[k] < array[indexMin]:
                indexMin = k
            k += 1
        array[i], array[indexMin] = array[indexMin], array[i]
    return array

if __name__ == '__main__':
    print(selectionSort(array_to_sort))

単純交換法(バブルソート

# bubble.py
array_to_sort = [5, 3, 4, 1, 2]

def bubbleSort(array):
    k = 0 # 確定させるインデックス
    while k < (len(array) - 1):
        # 一番後ろのインデックスから隣同士の要素を比較   
        i = len(array) - 1
        while k < i:
            if array[i-1] > array[i]:
                array[i-1], array[i] = array[i], array[i-1]
            i -= 1
        k += 1
    return array

if __name__ == '__main__':
    print(bubbleSort(array_to_sort))

単純挿入法(挿入ソート)

# insertion.py
array_to_sort = [5, 3, 4, 1, 2]

def insertionSort(array):
    i = 1
    while i < len(array):
        tmp = array[i]
        k = i
        while array[k-1] > tmp and k > 0:
            array[k] = array[k-1]
            k -= 1
        array[k] = tmp
        i += 1
    return array

if __name__ == '__main__':
    print(insertionSort(array_to_sort))

クイックソート

# quick.py
array_to_sort = [5, 4, 7, 6, 8, 3, 1, 2, 9]

def quickSort(array, left, right):
    i = left + 1
    k = right
    while i < k:
        while (array[i] < array[left]) and (i < right):
            i += 1
        while (array[left] <= array[k]) and (left < k):
            k -= 1
        if i < k:
            array[i], array[k] = array[k], array[i]
    if ((right - left) != 1) or (array[left] > array[k]):
        array[left], array[k] = array[k], array[left]
    if left < (k - 1):
        quickSort(array, left, k - 1)
    if (k + 1) < right:
        quickSort(array, k + 1, right)
    return array

if __name__ == '__main__':
    print(quickSort(array_to_sort, 0, len(array_to_sort) - 1))

エラトステネスのふるい(素数を求めるアルゴリズム

# eratosthenes.py
# 100までの数の素数を求める
array = [1 for i in range(101)]

def sieve(array):
    k = 2
    while k * k <= len(array):
        i = k
        while i <= (len(array) - 1) // k:
            array[i * k] = 0
            i += 1
        while True:
            k += 1
            if array[k] == 1:
                break
    output = []    
    for i in range(2, len(array)):
        if array[i] == 1:
            output.append(i)
    return output

if __name__ == '__main__':
    print(sieve(array))

ユークリッドの互除法(最大公約数を求めるアルゴリズム

# euclidean.py
num1, num2 = map(int, input().split())

def euclideanAlgo(num1, num2):
    if num1 > num2:
        a, b = num1, num2
    else:
        a, b = num2, num1
    r = a % b
    while r != 0:
        a, b = b, r
        r = a % b
    return b

if __name__ == '__main__':
    print(euclideanAlgo(num1, num2))


以上、基本的アルゴリズム(by Python)。
なるべくビルトイン関数を利用しないような形で書いてみました。
サンプルで書いてある配列は勉強した本で解説されている例と同じものを使っているので、参考にしてもらえれば良いかと。
もっと効率よくとか、こんな書き方はナンセンスだとか意見があったらお願いします。