Computer Science - Python - 探索とソート(挿入ソート(insertion 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-2-b.を解いてみる。

11.7(練習問題)、11-2-b..

書くイテレーション終了後のリストの内容の変化。

0. [6, 5, 4, 3, 7, 1, 2]
1. [6, 5, 4, 3, 7, 1, 2]
2. [5, 6, 4, 3, 7, 1, 2]
3. [4, 5, 6, 3, 7, 1, 2]
4. [3, 4, 5, 6, 7, 1, 2]
5. [3, 4, 5, 6, 7, 1, 2]
6. [1, 3, 4, 5, 6, 7, 2]
7. [1, 2, 3, 4, 5, 6, 7]

確認。

コード(BBEdit)

sample.py

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

def insertionSort(l):
    i = 0
    print(l)
    while i != len(l):
        insert(l, i)
        print(l)
        i = i + 1

def insert(items, b):
    i = b
    while i != 0 and l[i- 1] >= l[b]:
        i = i - 1
    v = l.pop(b)
    l.insert(i, v)

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

if __name__ == '__main__':
    insertionSort(l)

入出力結果(Terminal)

$ ./sample.py
[6, 5, 4, 3, 7, 1, 2]
[6, 5, 4, 3, 7, 1, 2]
[5, 6, 4, 3, 7, 1, 2]
[4, 5, 6, 3, 7, 1, 2]
[3, 4, 5, 6, 7, 1, 2]
[3, 4, 5, 6, 7, 1, 2]
[1, 3, 4, 5, 6, 7, 2]
[1, 2, 3, 4, 5, 6, 7]
$