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-4.を解いてみる。

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

コード(BBEdit)

sample.py

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

import nose

def bubbleSort(l):
    result = l[:]
    i = len(result) - 1
    for b in range(0, len(result) - 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 = len(result) - 1
    return result

# ソートの過程を表示
def bubbleSort1(l):
    result = l[:]
    print(result)
    i = len(result) - 1
    for b in range(0, len(result) - 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 = len(result) - 1
    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]
0
[6, 5, 4, 3, 7, 1, 2]
[6, 5, 4, 3, 1, 7, 2]
[6, 5, 4, 1, 3, 7, 2]
[6, 5, 1, 4, 3, 7, 2]
[6, 1, 5, 4, 3, 7, 2]
[1, 6, 5, 4, 3, 7, 2]
1
[1, 6, 5, 4, 3, 2, 7]
[1, 6, 5, 4, 2, 3, 7]
[1, 6, 5, 2, 4, 3, 7]
[1, 6, 2, 5, 4, 3, 7]
[1, 2, 6, 5, 4, 3, 7]
2
[1, 2, 6, 5, 4, 3, 7]
[1, 2, 6, 5, 3, 4, 7]
[1, 2, 6, 3, 5, 4, 7]
[1, 2, 3, 6, 5, 4, 7]
3
[1, 2, 3, 6, 5, 4, 7]
[1, 2, 3, 6, 4, 5, 7]
[1, 2, 3, 4, 6, 5, 7]
4
[1, 2, 3, 4, 6, 5, 7]
[1, 2, 3, 4, 5, 6, 7]
5
[1, 2, 3, 4, 5, 6, 7]
nose test
......
----------------------------------------------------------------------
Ran 6 tests in 0.002s

OK
$