Computer Science - Python - 探索とソート(バブルソート(bubble 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-3.を解いてみる。

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

コード(BBEdit)

sample.py

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

import nose

def bubbleSort(l):
    result = l[:]
    i = 0
    for b in range(len(l) - 1, 0, -1):
        while i < b:
            if result[i] > result[i + 1]:
                temp = result[i]
                result[i] = result[i + 1]
                result[i + 1] = temp
            i += 1
        i = 0
    return result

# ソートの過程を表示
def bubbleSort1(l):
    print(l)
    result = l[:]
    i = 0
    for b in range(len(l) - 1, 0, -1):
        print(b)
        while i < b:
            if result[i] > result[i + 1]:
                temp = result[i]
                result[i] = result[i + 1]
                result[i + 1] = temp
            i += 1
            print(result)
        i = 0
    return result

l = [6, 5, 4, 3, 7, 1, 2]

def run(original, expected):
    '''元ノリスとをソートし、模範解答と比較'''
    result = bubbleSort(original)
    assert result == 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__':
    bubbleSort1(l)
    print('nose test')
    nose.runmodule()

入出力結果(Terminal)

$ ./sample.py
[6, 5, 4, 3, 7, 1, 2]
6
[5, 6, 4, 3, 7, 1, 2]
[5, 4, 6, 3, 7, 1, 2]
[5, 4, 3, 6, 7, 1, 2]
[5, 4, 3, 6, 7, 1, 2]
[5, 4, 3, 6, 1, 7, 2]
[5, 4, 3, 6, 1, 2, 7]
5
[4, 5, 3, 6, 1, 2, 7]
[4, 3, 5, 6, 1, 2, 7]
[4, 3, 5, 6, 1, 2, 7]
[4, 3, 5, 1, 6, 2, 7]
[4, 3, 5, 1, 2, 6, 7]
4
[3, 4, 5, 1, 2, 6, 7]
[3, 4, 5, 1, 2, 6, 7]
[3, 4, 1, 5, 2, 6, 7]
[3, 4, 1, 2, 5, 6, 7]
3
[3, 4, 1, 2, 5, 6, 7]
[3, 1, 4, 2, 5, 6, 7]
[3, 1, 2, 4, 5, 6, 7]
2
[1, 3, 2, 4, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7]
1
[1, 2, 3, 4, 5, 6, 7]
nose test
......
----------------------------------------------------------------------
Ran 6 tests in 0.002s

OK
$