Algorithm - Python - 整理が苦手な修理屋(クイックソート、ピボット、移動個数、近似式、インプレースピボット決め、再帰インプレースソート)

問題解決の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章(整理が苦手な修理屋)、練習問題(問題1)を取り組んでみる。

コード(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:
            bottom += 1
            if bottom == top:
                done = True
                break
            if lst[bottom] > pivot:
                lst[top] = lst[bottom]
                move_count += 1
                break
        while not done:
            top -= 1
            if top == bottom:
                done = True
                break
            if lst[top] <= pivot:
                lst[bottom] = lst[top]
                move_count += 1
                break
    lst[top] = pivot
    return top, move_count


def quick_sort(lst: list, start: int, end: int) -> None:
    '''
    >>> a = [4, 65, 2, -31, 0, 99, 83, 782, 1]
    >>> quick_sort(a, 0, len(a) - 1)
    9
    >>> a
    [-31, 0, 1, 2, 4, 65, 83, 99, 782]
    >>> l = list(range(100))
    >>> quick_sort(l, 0, len(l) - 1)
    0
    >>> d = list(range(99, -1, -1))
    >>> quick_sort(d, 0, len(d) - 1)
    50
    >>> d = list(range(-1, -1, -1))
    >>> quick_sort(d, 0, len(d) - 1)
    0
    >>> d = list(range(0, -1, -1))
    >>> quick_sort(d, 0, len(d) - 1)
    0
    >>> d = list(range(1, -1, -1))
    >>> quick_sort(d, 0, len(d) - 1)
    1
    >>> d = list(range(10, -1, -1))
    >>> quick_sort(d, 0, len(d) - 1)
    5
    >>> d = list(range(11, -1, -1))
    >>> quick_sort(d, 0, len(d) - 1)
    6
    '''
    move_count = 0
    if start < end:
        pivot_index, count = pivot_partition_clever(lst, start, end)
        move_count += count
        move_count += quick_sort(lst, start, pivot_index - 1)
        move_count += quick_sort(lst, pivot_index + 1, end)
    return move_count


if __name__ == '__main__':
    import doctest
    doctest.testmod()
    # 要素数nの場合の近似式 n // 2

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

$ ./sample1.py -v
Trying:
    a = [4, 65, 2, -31, 0, 99, 83, 782, 1]
Expecting nothing
ok
Trying:
    quick_sort(a, 0, len(a) - 1)
Expecting:
    9
ok
Trying:
    a
Expecting:
    [-31, 0, 1, 2, 4, 65, 83, 99, 782]
ok
Trying:
    l = list(range(100))
Expecting nothing
ok
Trying:
    quick_sort(l, 0, len(l) - 1)
Expecting:
    0
ok
Trying:
    d = list(range(99, -1, -1))
Expecting nothing
ok
Trying:
    quick_sort(d, 0, len(d) - 1)
Expecting:
    50
ok
Trying:
    d = list(range(-1, -1, -1))
Expecting nothing
ok
Trying:
    quick_sort(d, 0, len(d) - 1)
Expecting:
    0
ok
Trying:
    d = list(range(0, -1, -1))
Expecting nothing
ok
Trying:
    quick_sort(d, 0, len(d) - 1)
Expecting:
    0
ok
Trying:
    d = list(range(1, -1, -1))
Expecting nothing
ok
Trying:
    quick_sort(d, 0, len(d) - 1)
Expecting:
    1
ok
Trying:
    d = list(range(10, -1, -1))
Expecting nothing
ok
Trying:
    quick_sort(d, 0, len(d) - 1)
Expecting:
    5
ok
Trying:
    d = list(range(11, -1, -1))
Expecting nothing
ok
Trying:
    quick_sort(d, 0, len(d) - 1)
Expecting:
    6
ok
2 items had no tests:
    __main__
    __main__.pivot_partition_clever
1 items passed all tests:
  17 tests in __main__.quick_sort
17 tests in 3 items.
17 passed and 0 failed.
Test passed.
$