Computer Science - Python - 探索とソート(挿入ソート、選択ソートとバブルソートのパフォーマンスを比較)

初めてのコンピュータサイエンス
(オライリージャパン)
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-5.を解いてみる。

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

コード(BBEdit)

sample.py

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

import time

def printTimes(l):
    print(len(l))
    for f in (selectionSort, insertionSort, bubbleSort):
        l_copy = l[:]
        t1 = time.time()
        f(l)
        t2 = time.time()
        print('{0:13s}:{1:6.1f}ms'.format(f.__name__, (t2 - t1) * 1000))
    print()

def selectionSort(l):
    i = 0
    while i != len(l):
        smallest = findMin(l, i)
        l[i], l[smallest] = l[smallest], l[i]
        i += 1

def findMin(l, i):
    smallest = i
    i += 1
    while i != len(l):
        if l[i] < l[smallest]:
            smallest = i
        i += 1
    return smallest

def insertionSort(l):
    i = 0
    while i != len(l):
        insert(l, i)
        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)

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

if __name__ == '__main__':
    for size in [10, 1000, 2000, 3000, 4000]:
        l = list(range(size))
        l.reverse()
        printTimes(l)

入出力結果(Terminal)

$ ./sample.py
10
selectionSort:   0.1ms
insertionSort:   0.0ms
bubbleSort   :   0.0ms

1000
selectionSort: 185.6ms
insertionSort:   2.9ms
bubbleSort   : 170.3ms

2000
selectionSort: 736.1ms
insertionSort:   9.2ms
bubbleSort   : 663.4ms

3000
selectionSort:1670.9ms
insertionSort:  14.1ms
bubbleSort   :1516.1ms

4000
selectionSort:2969.7ms
insertionSort:  23.9ms
bubbleSort   :2683.2ms

$

降順のリストを昇順にソートする場合は、挿入ソートが速い。(交換の必要がないから。)