[python] selection sort の勉強

Code

from typing import List
import time


def selection_sort(numbers: List[int]) -> List[int]:
    # 左から順番に選択
    for i in range(len(numbers)):
        min_idx = i

           # 基準より右側を順番に比較する。
        for j in range(i+1, len(numbers)):

            # 基準(min_idx)よりも右側に小さい値があれば交換候補とする。
            if numbers[min_idx] > numbers[j]:
                min_idx = j

        # 交換する
        numbers[i], numbers[min_idx] = numbers[min_idx], numbers[i]
    return numbers


if __name__ == '__main__':
    start = time.time()
    import random
    nums = [random.randint(0, 1000) for _ in range(10)]
    selection_sort(nums)
    print(time.time() - start)

かかった時間

0.006142139434814453
0.005542755126953125
0.004999876022338867

作業の可視化

[393, 188, 134, 629, 638, 461, 364, 51, 79, 209]
[51, 188, 134, 629, 638, 461, 364, 393, 79, 209]
[51, 79, 134, 629, 638, 461, 364, 393, 188, 209]
[51, 79, 134, 629, 638, 461, 364, 393, 188, 209]
[51, 79, 134, 188, 638, 461, 364, 393, 629, 209]
[51, 79, 134, 188, 209, 461, 364, 393, 629, 638]
[51, 79, 134, 188, 209, 364, 461, 393, 629, 638]
[51, 79, 134, 188, 209, 364, 393, 461, 629, 638]
[51, 79, 134, 188, 209, 364, 393, 461, 629, 638]
[51, 79, 134, 188, 209, 364, 393, 461, 629, 638]
[51, 79, 134, 188, 209, 364, 393, 461, 629, 638]

左の０番目から順番に順序が確定し、10個の要素の列に対して10回の作業で完了した。

どの位まで、できるかテスト

if __name__ == '__main__':
    for power in range(1, 10):
        start = time.time()
        import random
        nums = [random.randint(0, 1000) for _ in range(10**power)]
        selection_sort(nums)
        print('elements:', 10**power, 'time:', time.time() - start)

elements: 10 time: 0.0049970149993896484
elements: 100 time: 0.001001119613647461
elements: 1000 time: 0.052506208419799805
elements: 10000 time: 4.589069604873657
...

要素が約10000個以上からは、かなり時間がかかり、実用的ではないことがわかる。
100000個は60秒以上待っても結果が出てこなかった。

おわりに

前回勉強したbogo sort よりは、はるかに軽くて実用的であると思ったが、思ったよりは限界能力が低い。
しかしselection sortはとても有名であるので、抑えておくことは重要であるそうです。