Python - Searching and Sorting - merge sort

開発環境

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

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

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

Kamimura's blog

2020年5月20日水曜日

Python - Searching and Sorting - merge sort

0 コメント:

コメントを投稿