## 2020年5月13日水曜日

### Python - Searching and Sorting - Selection sort, Insertion sort

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()
```

```% ./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
%
```