データ構造操作

ソート

bubbleソート

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


if __name__ == '__main__':
    import random

    nums = [random.randint(0, 1000) for i in range(10)]
    bubble_sort(nums)

insertionソート

from typing import List


def insertion_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    for i in range(1, len_numbers):
        temp = numbers[i]
        j = i - 1
        while j >= 0 and numbers[j] > temp:
            numbers[j + 1] = numbers[j]
            j -= 1
        numbers[j + 1] = temp
    return numbers


if __name__ == '__main__':
    import random

    nums = [random.randint(0, 1000) for _ in random(10)]
    insertion_sort(nums)

selectソート

from typing import List


def selection_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    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


if __name__ == '__main__':
    import random

    nums = [random.randint(0, 1000) for _ in range(10)]
    selection_sort(nums)

quickソート

from typing import List


def partition(numbers: List[int], low: int, high: int) -> int:
    i = low - 1
    pivot = numbers[high]
    for j in range(low, high):
        if numbers[j] <= pivot:
            i += 1
            numbers[i], numbers[j] = numbers[j], numbers[i]
    numbers[i + 1], numbers[high] = numbers[high], numbers[i + 1]
    return i + 1


def quick_sort(numbers: List[int]) -> List[int]:
    def _quick_sort(numbers: List[int], low: int, high: int) -> None:
        if low < high:
            partition_index = partition(numbers, low, high)
            _quick_sort(numbers, low, partition_index - 1)
            _quick_sort(numbers, partition_index + 1, high)

    _quick_sort(numbers, 0, len(numbers) - 1)
    return numbers


if __name__ == '__main__':
    import random

    num = [random.randint(0, 1000) for _ in range(10)]
    quick_sort(num)

リンクリスト

キュー&スタック

キュー

from typing import Any


class Queue(object):
    def __init__(self):
        self.queue = []

    # データ追加
    def enqueue(self, data: Any) -> None:
        self.queue.append(data)

    # データ取り出し
    def dequeue(self, data: Any) -> Any:
        if self.queue:
            return self.queue.pop(0)


if __name__ == '__main__':
    q = Queue()
    q.enqueue(1)
    q.dequeue(1)

スタック

from typing import Any


class Stack(object):
    def __init__(self) -> None:
        self.stack = []

    def push(self, data) -> None:
        self.stack.append(data)

    def pop(self) -> Any:
        if self.stack:
            return self.stack.pop()


if __name__ == '__main__':
    stack = Stack()
    stack.push(1)
    stack.pop()

サーチ

リニアサーチ

from typing import List, NewType

# 新しい型を定義
IndexNum = NewType("IndexNum", int)


def linear_search(numbers: List[int], value: int) -> IndexNum:
    for i in range(0, len(numbers)):
        if numbers[i] == value:
            return i
    # もし存在しなかったら-1を返す
    return -1

バイナリサーチ

def binary_search(numbers: List[int], value: int) -> IndexNum:
    left, right = 0, len(numbers) - 1
    while left < right:
        mid = (left + right) // 2
        if numbers[mid] == value:
            return mid
        elif numbers[mid] < value:
            left = mid + 1
        else:
            right = mid - 1
    return -1


#リカージョンで記述した時。

def binary_search(numbers: List[int], value: int) -> IndexNum:
    def _binary_search(numbers: List[int], value,
                       left: IndexNum, right: IndexNum) -> IndexNum:
        if left > right:
            return -1
        mid = (left + right) // 2
        if numbers[mid] == value:
            return mid
        elif numbers < value:
            return _binary_search(numbers, value, mid + 1, right)
        else:
            return _binary_search(numbers, value, left, mid - 1)

    return _binary_search(numbers, value, 0, len(numbers) - 1)


if __name__ == '__main__':
    num = [0, 1, 3, 5, 6, 11, 25, 40]

ハッシュテーブル

import hashlib


class HashTable(object):
    def __init__(self, size=10) -> None:
        self.size = size
        self.table = [[] for _ in range(self.size)]

    def hash(self, key) -> int:
        #１６進数で帰ってくる
        # initのsizeで割ると余りがでてsizeに分けられる
        return int(hashlib.md5(key.encode()).hexdigest(), base=16) % self.size

    def add(self, key, value) -> None:
        index = self.hash(key)
        for data in self.table[index]:
            if data[0] == key:
                data[1] = value
                break
        else:
            self.table[index].append([key, value])

    def print(self) -> None:
        for index in range(self.size):
            #endで改行なしのprint
            for data in self.table[index]:
                print('-->', end=' ')
                print(data, end=' ')
            print()

    from typing import Any
    def get(self, key) -> Any:
        index = self.hash(key)
        for data in self.table[index]:
            if data[0] == key:
                return data[1]


if __name__ == '__main__':
    hash_table = HashTable()
    hash_table.add("car", "mamushi")
    hash_table.add("car", "ms")
    hash_table.table

二分木

class Node(object):
    def __init__(self, value: int) -> None:
        self.value = value
        self.left = None
        self.right = None