プログラミング学習の記録 632.3 11章(探索とソート)の練習問題5 『初めてのコンピュータサイエンス』(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(練習問題), 5を解いてみる。

 

5.

時間計測プログラムを挿入ソート、選択ソートとバブルソートを比較できるように書き換えたプログラム

コード

import time
from sort7 import insertion_sort
from sort4 import selection_sort
from bubble_sort import bubble_sort

def built_in(L):
    '''Call list.sort --- we need our own function to do this
    so that we can treat it as we treat our own sorts.'''
    L.sort()

def print_times(L):
    '''Print the number of milliseconds it takes for selection sort
    and insertion sort to run.'''

    print len(L),
    for func in (insertion_sort,selection_sort, bubble_sort, built_in):
        if func in (insertion_sort,selection_sort, bubble_sort) and len(L) > 4000:
            continue
            
        L_copy = L[:]
        t1 = time.time()
        func(L_copy)
        t2 = time.time()
        print "\t%.1f" % ((t2 - t1) * 1000.),
    print

for list_size in [10, 1000, 2000, 3000, 4000, 5000, 10000, 20000, 40000, 80000]:
    L = range(list_size)
    L.reverse()
    print_times(L)

計測結果

入出力結果(Python Shell)

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 30 lines of code... 10 0.0 0.0 0.0 0.0 1000 157.1 170.6 323.5 0.0 2000 612.3 756.6 1317.8 0.1 3000 1364.0 1748.5 3035.7 0.1 4000 2458.4 2779.1 5371.4 0.2 5000 0.2 10000 0.4 20000 0.8 40000 1.6 80000 3.7 >>>

結果から、バブルソートは他のソートより時間がかかることが分かる。挿入ソートと選択ソートについては本章に記述してある通り。