bubble_sort

ソースコード

from titan_pylib.algorithm.sort.bubble_sort import bubble_sort

view on github

展開済みコード

 1# from titan_pylib.algorithm.sort.bubble_sort import bubble_sort
 2# from titan_pylib.my_class.supports_less_than import SupportsLessThan
 3from typing import Protocol
 4
 5
 6class SupportsLessThan(Protocol):
 7
 8    def __lt__(self, other) -> bool: ...
 9from typing import TypeVar, Callable
10
11T = TypeVar("T", bound=SupportsLessThan)
12
13
14def bubble_sort(
15    a: list[T], key: Callable[[T, T], bool] = lambda s, t: s < t, inplace: bool = True
16) -> list[T]:
17    """バブルソートです。
18
19    非破壊的です。
20    最悪 :math:`O(n^2)` 時間です。
21
22    Args:
23        a (Iterable[T]): ソートする列です。
24        key (Callable[[T, T], bool], optional): 比較関数 `key` にしたがって比較演算をします。
25                                                (第1引数)<(第2引数) のとき、 ``True`` を返すようにしてください。
26    """
27    a = a[:] if inplace else a
28    n = len(a)
29    for i in range(n):
30        flag = True
31        for j in range(n - 1, i - 1, -1):
32            if not key(a[j - 1], a[j]):
33                a[j], a[j - 1] = a[j - 1], a[j]
34                flag = False
35        if flag:
36            break
37    return a

仕様

bubble_sort(a: list[~titan_pylib.algorithm.sort.bubble_sort.T], key: ~typing.Callable[[~titan_pylib.algorithm.sort.bubble_sort.T, ~titan_pylib.algorithm.sort.bubble_sort.T], bool] = <function <lambda>>, inplace: bool = True) → list[T][source]

バブルソートです。

非破壊的です。 最悪 \(O(n^2)\) 時間です。

Parameters:

  • a (Iterable[T]) – ソートする列です。

  • key (Callable[[T, T], bool], optional) – 比較関数 key にしたがって比較演算をします。 (第1引数)<(第2引数) のとき、 True を返すようにしてください。