プログラミング学習の記録 629.3 11章(探索とソート)の練習問題2 『初めてのコンピュータサイエンス』(Jennifer Campbell, Paul Gries, Jason Montojo, Greg Wilson 著、長尾 高弘 訳、オライリー・ジャパン、2010年、ISBN978-4-87311-463-7)

開発環境

• Mac OS X Snow Leopard (OS)
• WingIDE
• Script言語: Python

『初めてのコンピュータサイエンス』(Jennifer Campbell, Paul Gries, Jason Montojo, Greg Wilson 著、長尾 高弘 訳、オライリー・ジャパン、2010年、ISBN978-4-87311-463-7)の11章(探索とソート), 11.7(練習問題), 2を解いてみる。

 

2.

ソートするリスト

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

選択ソート、挿入ソートのアルゴリズムを使ってこのリストをソートした時、ループの各イテレーション終了後、リストの内容がどう変わっていってるか。

(a) 選択ソートの場合

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

(b) 挿入ソートの場合

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]

確認

コード

def selection_sort(L):
    i=0
    while i!=len(L):
        smallest=find_min(L,i)
        L[i],L[smallest]=L[smallest],L[i]
        i=i+1
        print L
def find_min(L,b):
    smallest=b
    i=b+1
    while i!=len(L):
        if L[i]=L[b]:
        i=i-1
    value=L[b]
    del L[b]
    L.insert(i,value)

入出力結果

Python 2.6.6 (r266:84374, Aug 31 2010, 11:00:51) [GCC 4.0.1 (Apple Inc. build 5493)] Type "help", "copyright", "credits" or "license" for more information. >>> Evaluating 28 lines of code... >>> selection_sort([6,5,4,3,7,1,2]) [1, 5, 4, 3, 7, 6, 2] [1, 2, 4, 3, 7, 6, 5] [1, 2, 3, 4, 7, 6, 5] [1, 2, 3, 4, 7, 6, 5] [1, 2, 3, 4, 5, 6, 7] [1, 2, 3, 4, 5, 6, 7] [1, 2, 3, 4, 5, 6, 7] >>> insertion_sort([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] >>>

確認できた！