2020年5月20日水曜日

Python - Searching and Sorting - merge 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 10の解答を求めてみる。

コード

```#!/usr/bin/env python3
from unittest import TestCase, main

print('10.')

class TestMergeSort(TestCase):
def test_merge(self):
self.assertEqual(merge([1, 3, 4, 6], [1, 2, 5, 7]),
[1, 1, 2, 3, 4, 5, 6, 7])

def test_empty(self):
l = []
merge_sort(l)
self.assertEqual(l, [])

def test_one(self):
l = [1]
merge_sort(l)
self.assertEqual(l, [1])

def test_descent(self):
l = [2, 1]
merge_sort(l)
self.assertEqual(l, [1, 2])

def test_ascent(self):
l = [1, 2]
merge_sort(l)
self.assertEqual(l, [1, 2])

def test_duplicate(self):
l = [3, 3, 3]
merge_sort(l)
self.assertEqual(l, [3, 3, 3])

def test_general(self):
l = [3, 4, 7, -1, 2, 5]
merge_sort(l)
self.assertEqual(l, [-1, 2, 3, 4, 5, 7])

def test_general_duplicate(self):
l = [-5, 3, 0, 3, -6, 2, 1, 1]
merge_sort(l)
self.assertEqual(l, [-6, -5, 0, 1, 1, 2, 3, 3])

def merge(l1: list, l2: list) -> list:
new_l: list = []
i1: int = 0
i2: int = 0
while i1 != len(l1) or i2 != len(l2):
print(i1, i2, l2)
if i1 == len(l1) or (i2 != len(l2) and l2[i2] <= l1[i1]):
new_l.append(l2[i2])
i2 += 1
else:
new_l.append(l1[i1])
i1 += 1
return new_l

def merge_sort(l: list) -> None:
workspace = [[v] for v in l]
i = 0
while i < len(workspace) - 1:
new_l = merge(workspace[i], workspace[i + 1])
workspace.append(new_l)
i += 2
if len(workspace) != 0:
l[:] = workspace[-1][:]

if __name__ == "__main__":
main()
```

```% ./sample10.py
10.
.F..FFF.
======================================================================
FAIL: test_descent (__main__.TestMergeSort)
----------------------------------------------------------------------
Traceback (most recent call last):
File "./sample10.py", line 25, in test_descent
self.assertEqual(l, [1, 2])
AssertionError: Lists differ: [2, 1] != [1, 2]

First differing element 0:
2
1

- [2, 1]
+ [1, 2]

======================================================================
FAIL: test_general (__main__.TestMergeSort)
----------------------------------------------------------------------
Traceback (most recent call last):
File "./sample10.py", line 40, in test_general
self.assertEqual(l, [-1, 2, 3, 4, 5, 7])
AssertionError: Lists differ: [3, 4, 7, -1, 2, 5] != [-1, 2, 3, 4, 5, 7]

First differing element 0:
3
-1

- [3, 4, 7, -1, 2, 5]
+ [-1, 2, 3, 4, 5, 7]

======================================================================
FAIL: test_general_duplicate (__main__.TestMergeSort)
----------------------------------------------------------------------
Traceback (most recent call last):
File "./sample10.py", line 45, in test_general_duplicate
self.assertEqual(l, [-6, -5, 0, 1, 1, 2, 3, 3])
AssertionError: Lists differ: [-5, 3, 0, 3, -6, 2, 1, 1] != [-6, -5, 0, 1, 1, 2, 3, 3]

First differing element 0:
-5
-6

- [-5, 3, 0, 3, -6, 2, 1, 1]
+ [-6, -5, 0, 1, 1, 2, 3, 3]

======================================================================
FAIL: test_merge (__main__.TestMergeSort)
----------------------------------------------------------------------
Traceback (most recent call last):
File "./sample10.py", line 9, in test_merge
self.assertEqual(merge([1, 3, 4, 6], [1, 2, 5, 7]),
AssertionError: None != [1, 1, 2, 3, 4, 5, 6, 7]

----------------------------------------------------------------------
Ran 8 tests in 0.001s

FAILED (failures=4)
% ./sample10.py
10.
.F..FF0 0 [1, 2, 5, 7]
0 1 [1, 2, 5, 7]
1 1 [1, 2, 5, 7]
1 2 [1, 2, 5, 7]
2 2 [1, 2, 5, 7]
3 2 [1, 2, 5, 7]
3 3 [1, 2, 5, 7]
4 3 [1, 2, 5, 7]
..
======================================================================
FAIL: test_descent (__main__.TestMergeSort)
----------------------------------------------------------------------
Traceback (most recent call last):
File "./sample10.py", line 25, in test_descent
self.assertEqual(l, [1, 2])
AssertionError: Lists differ: [2, 1] != [1, 2]

First differing element 0:
2
1

- [2, 1]
+ [1, 2]

======================================================================
FAIL: test_general (__main__.TestMergeSort)
----------------------------------------------------------------------
Traceback (most recent call last):
File "./sample10.py", line 40, in test_general
self.assertEqual(l, [-1, 2, 3, 4, 5, 7])
AssertionError: Lists differ: [3, 4, 7, -1, 2, 5] != [-1, 2, 3, 4, 5, 7]

First differing element 0:
3
-1

- [3, 4, 7, -1, 2, 5]
+ [-1, 2, 3, 4, 5, 7]

======================================================================
FAIL: test_general_duplicate (__main__.TestMergeSort)
----------------------------------------------------------------------
Traceback (most recent call last):
File "./sample10.py", line 45, in test_general_duplicate
self.assertEqual(l, [-6, -5, 0, 1, 1, 2, 3, 3])
AssertionError: Lists differ: [-5, 3, 0, 3, -6, 2, 1, 1] != [-6, -5, 0, 1, 1, 2, 3, 3]

First differing element 0:
-5
-6

- [-5, 3, 0, 3, -6, 2, 1, 1]
+ [-6, -5, 0, 1, 1, 2, 3, 3]

----------------------------------------------------------------------
Ran 8 tests in 0.001s

FAILED (failures=3)
% ./sample10.py
10.
0 0 [2]
1 0 [2]
.0 0 [1]
0 1 [1]
.0 0 [3]
0 1 [3]
0 0 [3, 3]
0 1 [3, 3]
0 2 [3, 3]
..0 0 [4]
1 0 [4]
0 0 [-1]
0 1 [-1]
0 0 [5]
1 0 [5]
0 0 [-1, 7]
0 1 [-1, 7]
1 1 [-1, 7]
2 1 [-1, 7]
0 0 [-1, 3, 4, 7]
0 1 [-1, 3, 4, 7]
1 1 [-1, 3, 4, 7]
1 2 [-1, 3, 4, 7]
1 3 [-1, 3, 4, 7]
2 3 [-1, 3, 4, 7]
.0 0 [3]
1 0 [3]
0 0 [3]
1 0 [3]
0 0 [2]
1 0 [2]
0 0 [1]
0 1 [1]
0 0 [0, 3]
1 0 [0, 3]
1 1 [0, 3]
1 2 [0, 3]
0 0 [1, 1]
1 0 [1, 1]
1 1 [1, 1]
1 2 [1, 1]
0 0 [-6, 1, 1, 2]
0 1 [-6, 1, 1, 2]
1 1 [-6, 1, 1, 2]
2 1 [-6, 1, 1, 2]
2 2 [-6, 1, 1, 2]
2 3 [-6, 1, 1, 2]
2 4 [-6, 1, 1, 2]
3 4 [-6, 1, 1, 2]
.0 0 [1, 2, 5, 7]
0 1 [1, 2, 5, 7]
1 1 [1, 2, 5, 7]
1 2 [1, 2, 5, 7]
2 2 [1, 2, 5, 7]
3 2 [1, 2, 5, 7]
3 3 [1, 2, 5, 7]
4 3 [1, 2, 5, 7]
..
----------------------------------------------------------------------
Ran 8 tests in 0.001s

OK
% mypy sample10.py
Success: no issues found in 1 source file
% ./sample10.py -v
10.
test_ascent (__main__.TestMergeSort) ... 0 0 [2]
1 0 [2]
ok
test_descent (__main__.TestMergeSort) ... 0 0 [1]
0 1 [1]
ok
test_duplicate (__main__.TestMergeSort) ... 0 0 [3]
0 1 [3]
0 0 [3, 3]
0 1 [3, 3]
0 2 [3, 3]
ok
test_empty (__main__.TestMergeSort) ... ok
test_general (__main__.TestMergeSort) ... 0 0 [4]
1 0 [4]
0 0 [-1]
0 1 [-1]
0 0 [5]
1 0 [5]
0 0 [-1, 7]
0 1 [-1, 7]
1 1 [-1, 7]
2 1 [-1, 7]
0 0 [-1, 3, 4, 7]
0 1 [-1, 3, 4, 7]
1 1 [-1, 3, 4, 7]
1 2 [-1, 3, 4, 7]
1 3 [-1, 3, 4, 7]
2 3 [-1, 3, 4, 7]
ok
test_general_duplicate (__main__.TestMergeSort) ... 0 0 [3]
1 0 [3]
0 0 [3]
1 0 [3]
0 0 [2]
1 0 [2]
0 0 [1]
0 1 [1]
0 0 [0, 3]
1 0 [0, 3]
1 1 [0, 3]
1 2 [0, 3]
0 0 [1, 1]
1 0 [1, 1]
1 1 [1, 1]
1 2 [1, 1]
0 0 [-6, 1, 1, 2]
0 1 [-6, 1, 1, 2]
1 1 [-6, 1, 1, 2]
2 1 [-6, 1, 1, 2]
2 2 [-6, 1, 1, 2]
2 3 [-6, 1, 1, 2]
2 4 [-6, 1, 1, 2]
3 4 [-6, 1, 1, 2]
ok
test_merge (__main__.TestMergeSort) ... 0 0 [1, 2, 5, 7]
0 1 [1, 2, 5, 7]
1 1 [1, 2, 5, 7]
1 2 [1, 2, 5, 7]
2 2 [1, 2, 5, 7]
3 2 [1, 2, 5, 7]
3 3 [1, 2, 5, 7]
4 3 [1, 2, 5, 7]
ok
test_one (__main__.TestMergeSort) ... ok

----------------------------------------------------------------------
Ran 8 tests in 0.001s

OK
%
```