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

コード(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_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)
    24
    '''
    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()
    r = [0] * 100
    r[0] = 19
    for i in range(100):
        r[i] = (9679 * r[i-1] + 12637 * i) % 2287
    count = quick_sort(r, 0, len(r) - 1)
    print(r)
    print(count)
    d = list(range(99, -1, -1))
    count = quick_sort(d, 0, len(d) - 1)
    print(d)
    print(count)
    '''
近似式 n log2 n
    '''
    import random
    import math
    n = 50
    m = 10000
    print(f'近似値: {n * math.log2(n)}')
    l = list(range(n))
    total = 0
    for _ in range(m):
        random.shuffle(l)
        total += quick_sort(l, 0, n - 1)
    print(total / m)

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

$ ./sample2.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:
    24
ok
2 items had no tests:
    __main__
    __main__.pivot_partition_clever
1 items passed all tests:
   2 tests in __main__.quick_sort
2 tests in 3 items.
2 passed and 0 failed.
Test passed.
[0, 38, 50, 116, 122, 141, 146, 220, 240, 240, 243, 275, 288, 305, 306, 306, 307, 387, 419, 431, 433, 446, 450, 493, 538, 548, 595, 598, 711, 764, 804, 812, 829, 844, 879, 910, 929, 942, 955, 967, 1038, 1041, 1049, 1078, 1083, 1102, 1105, 1150, 1153, 1154, 1172, 1202, 1208, 1221, 1244, 1266, 1266, 1290, 1320, 1384, 1386, 1425, 1428, 1476, 1505, 1517, 1520, 1523, 1553, 1582, 1609, 1613, 1625, 1639, 1691, 1696, 1725, 1818, 1845, 1884, 1927, 1938, 1946, 1949, 1980, 1991, 1995, 2006, 2029, 2038, 2047, 2085, 2107, 2115, 2119, 2125, 2188, 2215, 2269, 2284]
682
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
5049
近似値: 282.1928094887362
291.9067
$

DとRでループの回数が異なる理由は、Dの場合、ピボットが最小値で、分割の偏りがもっとも大きい場合に該当するから。