Computer Science - Python - 探索とソート(マージソード(merge sort))

初めてのコンピュータサイエンス
(オライリージャパン)
Jennifer Campbell Paul Gries
Jason Montojo Greg Wilson (著)
長尾 高弘 (翻訳)

開発環境

• OS X Mavericks - Apple(OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Python (プログラミング言語)

初めてのコンピュータサイエンス(Jennifer Campbell、Paul Gries、Jason Montojo、Greg Wilson(著)長尾 高弘(翻訳))の11章(探索とソート)、11.7(練習問題)、11-9.を解いてみる。

11.7(練習問題)、11-9.

コード(BBEdit)

sample.py

#!/usr/bin/env python3.3
#-*- coding: utf-8 -*-

import nose

def merge(l1, l2):
    new_l = []
    i1 = 0
    i2 = 0
    
    while True:
        if i1 == len(l1):
            for x in l2[i2:]:
                new_l.append(x)
            break
        if i2 == len(l2):
            for x in l1[i1:]:
                new_l.append(x)
            break
        if l1[i1] <= l2[i2]:
            new_l.append(l1[i1])
            i1 += 1
        else:
            new_l.append(l2[i2])
            i2 += 1
    
    return new_l

def mergeSort(l):
    workspace = []
    for i in range(len(l)):
        workspace.append([l[i]])
    
    i = 0
    
    while i < len(workspace) - 1:
        l1 = workspace[i]
        l2 = workspace[i + 1]
        new_l = merge(l1, l2)
        workspace.append(new_l)
        i += 2
    if len(workspace) != 0:
        l[:] = workspace[-1][:]

def run(original, expected):
    '''元ノリスとをソートし、模範解答と比較'''
    mergeSort(original)
    assert original == expected

def test_empty():
    '''空のリスト'''
    run([], [])

def test_one():
    '''要素が1個のリスト'''
    run([1], [1])

def test_two_ordered():
    '''要素が2個で既にソートされているリスト'''
    run([1, 2], [1, 2])

def test_two_reversed():
    '''要素が2個で逆順になっているリストのテスト'''
    run([2, 1], [1, 2])

def test_three_identical():
    '''3個の等しい値によるリストのテスト'''
    run([3, 3, 3], [3, 3, 3])

def test_three_split():
    '''異なる値が1つ混ざっているリストのテスト'''
    run([3, 0, 3], [0, 3, 3])

if __name__ == '__main__':
    nose.runmodule()

入出力結果(Terminal)

$ ./sample.py
......
----------------------------------------------------------------------
Ran 6 tests in 0.002s

OK
$