Python - Searching and Sorting - Selection sort, Insertion sort

Practical Programming
楽天ブックス 紀伊国屋書店

開発環境

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

Practical Programming: An Introduction to Computer Science Using Python 3.6 (Paul Gries(著)、Jennifer Campbell(著)、Jason Montojo(著)、Pragmatic Bookshelf)のChapter 13(Searching and Sorting)、Exercise 4の解答を求めてみる。

コード

#!/usr/bin/env python3
from unittest import TestCase, main
from test.support import captured_stdout

print('4-a, b.')


class TestEachIteration(TestCase):
    def setUp(self):
        self.lst = [6, 5, 4, 3, 7, 1, 2]

    def test_selection_sort(self):
        with captured_stdout() as stdout:
            selection_sort(self.lst)
        s = '''[1, 5, 4, 3, 7, 6, 2]
[1, 2, 4, 3, 7, 6, 5]
[1, 2, 3, 4, 7, 6, 5]
[1, 2, 3, 4, 7, 6, 5]
[1, 2, 3, 4, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7]
'''
        self.assertEqual(stdout.getvalue(), s)

    def test_insertion_sort(self):
        with captured_stdout() as stdout:
            insertion_sort(self.lst)
        s = '''[6, 5, 4, 3, 7, 1, 2]
[5, 6, 4, 3, 7, 1, 2]
[4, 5, 6, 3, 7, 1, 2]
[3, 4, 5, 6, 7, 1, 2]
[3, 4, 5, 6, 7, 1, 2]
[1, 3, 4, 5, 6, 7, 2]
[1, 2, 3, 4, 5, 6, 7]
'''
        self.assertEqual(stdout.getvalue(), s)


def find_min(l: list, b: int) -> int:
    smallest = b
    i = b + 1
    while i != len(l):
        if l[i] < l[smallest]:
            smallest = i
        i += 1
    return smallest


def selection_sort(l: list) -> None:
    i = 0
    while i != len(l):
        smallest = find_min(l, i)
        l[i], l[smallest] = l[smallest], l[i]
        print(l)
        i += 1


def insert(l: list, b: int) -> None:
    i = b
    while i != 0 and l[i - 1] >= l[b]:
        i -= 1
    v = l[b]
    del l[b]
    l.insert(i, v)


def insertion_sort(l: list) -> None:
    i = 0
    while i != len(l):
        insert(l, i)
        print(l)
        i += 1


if __name__ == "__main__":
    main()

入出力結果(Zsh、PowerShell、Terminal、Jupyter(IPython))

% ./sample4.py -v
4-a, b.
test_insertion_sort (__main__.TestEachIteration) ... ok
test_selection_sort (__main__.TestEachIteration) ... ok

----------------------------------------------------------------------
Ran 2 tests in 0.000s

OK
%