quick_sort

ソースコード

from titan_pylib.algorithm.sort.quick_sort import quick_sort

view on github

展開済みコード

 1# from titan_pylib.algorithm.sort.quick_sort import quick_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 Iterable, TypeVar, Callable
10import random
11
12T = TypeVar("T", bound=SupportsLessThan)
13
14
15def quick_sort(
16    a: Iterable[T], key: Callable[[T, T], bool] = lambda s, t: s < t
17) -> list[T]:
18    """クイックソートです。
19
20    非破壊的です。
21    期待 :math:`O(n\\log{n})` 時間です。
22
23    Args:
24        a (Iterable[T]): ソートする列です。
25        key (Callable[[T, T], bool], optional): 比較関数 `key` にしたがって比較演算をします。
26                                                (第1引数)<(第2引数) のとき、 ``True`` を返すようにしてください。
27    """
28    a = list(a)
29
30    def sort(i: int, j: int):
31        if i >= j:
32            return
33        pivot = a[random.randint(i, j)]
34        l, r = i, j
35        while True:
36            while key(a[l], pivot):
37                l += 1
38            while key(pivot, a[r]):
39                r -= 1
40            if l >= r:
41                break
42            a[l], a[r] = a[r], a[l]
43            l += 1
44            r -= 1
45        sort(i, l - 1)
46        sort(r + 1, j)
47
48    sort(0, len(a) - 1)
49    return a

仕様

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

クイックソートです。

非破壊的です。 期待 \(O(n\log{n})\) 時間です。

Parameters:

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

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