Pythonメモ : pygorithmで探索、ソートのアルゴリズムを学ぶ

pygorithm

---

github.com

pygorithmという探索、ソートなどのアルゴリズムを学ぶためのモジュールがあったので試してみる。

インストール

---

pipでインストールできるので下記コマンドを実行。

$ pip install pygorithm

が、少し試したところ最新バージョンではなかったのでGitHubのリポジトリをインストールした。

$ pip install git+https://github.com/OmkarPathak/pygorithm

使い方

---

バブルソートを例に試してみる。
まずはbubble_sortをインポートして実際にソートする。

from pygorithm.sorting import bubble_sort
myList = [12, 4, 3, 5, 13, 1, 17, 19, 15]
sortedList = bubble_sort.sort(myList)
print(sortedList)

ソート結果を出力する。

[1, 3, 4, 5, 12, 13, 15, 17, 19]

get_code()とすることでコードを取得できる。

from pygorithm.sorting import bubble_sort
code = bubble_sort.get_code()
print(code)

コードの出力結果。

def sort(List):
    for i in range(len(List)):
        for j in range(len(List) - 1, i, -1):
            if List[j] < List[j - 1]:
                List[j], List[j - 1] = List[j - 1], List[j]
    return List

time_complexities()で計算量を取得できる。

from pygorithm.sorting import bubble_sort
time_complexity = bubble_sort.time_complexities()
print(time_complexity)

計算量の出力結果。

Best Case: O(n ^ 2), Average Case: O(n ^ 2), Worst Case: O(n ^ 2)
 For Improved Bubble Sort:
 Best Case: O(n); Average Case: O(n * (n - 1) / 4); Worst Case: O(n ^ 2)

利用可能なモジュールはmodulesで確認できる。

>>> from pygorithm.sorting import modules
>>> modules()
['bubble_sort', 'bucket_sort', 'counting_sort', 'heap_sort', 'insertion_sort', 'merge_sort', 'quick_sort', 'selection_sort', 'shell_sort']

探索アルゴリズムの場合。

>>> from pygorithm.searching import modules
>>> modules()
['binary_search', 'breadth_first_search', 'depth_first_search', 'linear_search', 'quick_select']

二分探索を試してみる。

from pygorithm.searching import binary_search
code = binary_search.get_code()
print(code)
time_complexity = binary_search.time_complexities()
print(time_complexity)

実行結果。

def search(List, target):
    '''This function performs a binary search on a sorted list and returns the position if successful else returns -1'''
    left = 0                # First position of the list
    right = len(List) - 1   # Last position of the list

    try:
        found = False
        while left <= right:    # you can also write while True condition
            mid = (left + right) // 2
            if target == List[mid]:
                found = True
                return mid
            elif target < List[mid]:
                right =  mid - 1
            else:
                left = mid + 1
        if found == False:
            return -1
    except TypeError:
        return -1

Best Case: O(1), Average Case: O(logn), Worst Case: O(logn)

sorting, searchingの他にdata_structures, fibonacciという項目もあるようだ。

その他のアルゴリズムまとめリポジトリ

---

GitHubでスター数が多くて、頻繁に更新されているリポジトリを探してみた。

GitHub - donnemartin/interactive-coding-challenges: Huge update! Interactive Python coding interview challenges (algorithms and data structures). Includes Anki flashcards.
GitHub - keon/algorithms: Minimal examples of data structures and algorithms in Python
GitHub - nryoung/algorithms: An educational library of algorithms in Python
GitHub - TheAlgorithms/Python: All Algorithms implemented in Python

バブルソートを見てみたところ、それぞれで書き方が違うので色々と参考になるかも。

keon/algorithmsの場合。

def bubble_sort(arr):

    def swap(i, j):
        arr[i], arr[j] = arr[j], arr[i]

    n = len(arr)
    swapped = True
    while swapped:
        swapped = False
        for i in range(1, n):
            if arr[i - 1] > arr[i]:
                swap(i - 1, i)
                swapped = True

array = [1, 5, 65, 23, 57, 1232, -1, -5, -2, 242, 100,
         4, 423, 2, 564, 9, 0, 10, 43, 64, 32, 1, 999]
print(array)
bubble_sort(array)
print(array)

nryoung/algorithmsの場合。

def sort(seq):
    """
    Takes a list of integers and sorts them in ascending order. This sorted
    list is then returned.
    :param seq: A list of integers
    :rtype: A list of sorted integers
    """
    L = len(seq)
    for i in range(L):
        for n in range(1, L - i):
            if seq[n] < seq[n - 1]:
                seq[n - 1], seq[n] = seq[n], seq[n - 1]
    return seq