Algorithm - Python - 整理が苦手な修理屋(未ソート配列のk番目に小さい要素のの探索、再帰分割、インプレースピボット決め、再帰インプレースソート)

問題解決のPythonプログラミング
原著
楽天ブックス(Kobo) Yahoo!

開発環境

• macOS Mojave - Apple (OS)
• Emacs (Text Editor)
• Windows 10 Pro (OS)
• Visual Studio Code (Text Editor)
• Python 3.7 (プログラミング言語)

問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考 (Srini Devadas (著)、黒川 利明 (翻訳)、オライリージャパン)の13章(整理が苦手な修理屋)、練習問題(問題3)を取り組んでみる。

コード(Emacs)

Python 3

#!/usr/bin/env python3
def pivot_partition_clever(lst: list, start: int, end: int) -> (int, int):
    pivot = lst[end]
    bottom = start - 1
    top = end
    done = False
    move_count = 0
    while not done:
        while not done:
            move_count += 1
            bottom += 1
            if bottom == top:
                done = True
                break
            if lst[bottom] > pivot:
                lst[top] = lst[bottom]
                break
        while not done:
            move_count += 1
            top -= 1
            if top == bottom:
                done = True
                break
            if lst[top] <= pivot:
                lst[bottom] = lst[top]
                break
    lst[top] = pivot
    return top, move_count


def quick_select(lst: list, start: int, end: int, k: int) -> int:
    '''
    >>> quick_select([10], 0, 0, 1)
    10
    >>> quick_select([0, 1, 2, 3, 4], 0, 4, 1)
    0
    >>> quick_select([0, 1, 2, 3, 4], 0, 4, 5)
    4
    >>> quick_select([0, 1, 2, 3, 4], 0, 4, 2)
    1
    >>> quick_select([0, 1, 2, 3, 4], 0, 4, 3)
    2
    >>> quick_select([4, 65, 2, -31, 0, 99, 83, 782, 1], 0, 8, 1)
    -31
    >>> quick_select([4, 65, 2, -31, 0, 99, 83, 782, 1], 0, 8, 9)
    782
    >>> quick_select([4, 65, 2, -31, 0, 99, 83, 782, 1], 0, 8, 4)
    2
    >>> quick_select([4, 65, 2, -31, 0, 99, 83, 782, 1], 0, 8, 5)
    4
    '''
    if start < end:
        pivot_index, _ = pivot_partition_clever(lst, start, end)
        if pivot_index == k - 1:
            return lst[pivot_index]
        if pivot_index > k - 1:
            return quick_select(lst, start, pivot_index - 1, k)
        return quick_select(lst, pivot_index + 1, end, k)
    return lst[k - 1]


if __name__ == '__main__':
    import doctest
    doctest.testmod()

    import random
    n = 20
    l = list(range(n, 0, -1))
    print(l)
    print(sorted(l))
    for k in range(1, n + 1):
        random.shuffle(l)
        sorted_l = sorted(l)
        num = quick_select(l, 0, len(l) - 1, k)
        print(f'k = {k}, num = {num}, {sorted_l[k - 1]}, '
              f'{sorted_l[k - 1] == num}')

入出力結果(Terminal, cmd(コマンドプロンプト), Jupyter(IPython))

$ ./sample3.py -v
Trying:
    quick_select([0, 1, 2, 3, 4], 0, 4, 1)
Expecting:
    0
ok
Trying:
    quick_select([0, 1, 2, 3, 4], 0, 4, 5)
Expecting:
    4
ok
Trying:
    quick_select([0, 1, 2, 3, 4], 0, 4, 2)
Expecting:
    1
ok
Trying:
    quick_select([0, 1, 2, 3, 4], 0, 4, 3)
Expecting:
    2
ok
Trying:
    quick_select([4, 65, 2, -31, 0, 99, 83, 782, 1], 0, 8, 1)
Expecting:
    -31
ok
Trying:
    quick_select([4, 65, 2, -31, 0, 99, 83, 782, 1], 0, 8, 9)
Expecting:
    782
ok
Trying:
    quick_select([4, 65, 2, -31, 0, 99, 83, 782, 1], 0, 8, 4)
Expecting:
    2
ok
Trying:
    quick_select([4, 65, 2, -31, 0, 99, 83, 782, 1], 0, 8, 5)
Expecting:
    4
ok
2 items had no tests:
    __main__
    __main__.pivot_partition_clever
1 items passed all tests:
   8 tests in __main__.quick_select
8 tests in 3 items.
8 passed and 0 failed.
Test passed.
[20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
k = 1, num = 1, 1, True
k = 2, num = 2, 2, True
k = 3, num = 3, 3, True
k = 4, num = 4, 4, True
k = 5, num = 5, 5, True
k = 6, num = 6, 6, True
k = 7, num = 7, 7, True
k = 8, num = 8, 8, True
k = 9, num = 9, 9, True
k = 10, num = 10, 10, True
k = 11, num = 11, 11, True
k = 12, num = 12, 12, True
k = 13, num = 13, 13, True
k = 14, num = 14, 14, True
k = 15, num = 15, 15, True
k = 16, num = 16, 16, True
k = 17, num = 17, 17, True
k = 18, num = 18, 18, True
k = 19, num = 19, 19, True
k = 20, num = 20, 20, True
$