Python - Searching and Sorting(comparing the timing of bubble sort, insertion sort and selection sort)

Practical Programming
An Introduction to Computer Science
Using Python 3
(Pragmatic Programmers)
(Pragmatic Bookshelf)
Paul Gries (著) Jennifer Campbell (著)
Jason Montojo (著) Lynn Beighley (編集)

開発環境

• OS X Yosemite - Apple (OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Python 3.4 (プログラミング言語)

Practical Programming: An Introduction to Computer Science Using Python 3 (Pragmatic Programmers) (Paul Gries (著)、Jennifer Campbell (著)、Jason Montojo (著)、Lynn Beighley (編集)、Pragmatic Bookshelf)のChapter 13(Searching and Sorting)、13.7(Exercises) 7.を解いてみる。

13.7(Exercises) 7.

コード(BBEdit)

sample7.py

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

import time
import random

def built_in(L):
    L.sort()

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

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

def insert(L, b):
    i = b
    while i != 0 and L[i - 1] >= L[b]:
        i -= 1
    value = L[b]
    del L[b]
    L.insert(i, value)

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

def bubbleSort(l):
    i = 0
    m = len(l) - 1

    while m > 0:
        while i < m:
            if l[i] > l[i + 1]:
                l[i + 1], l[i] = l[i], l[i + 1]
            i += 1
        i = 0
        m -= 1

def printTimes(L):
    print(len(L), end='\t')
    for func in (selectionSort, insertionSort, bubbleSort, built_in):
        if func in (selectionSort, insertionSort, built_in) and len(L) > 10000:
            continue
        L_copy = L[:]
        t1 = time.perf_counter()
        func(L_copy)
        t2 = time.perf_counter()
        print('{0:7.1f}'.format((t2 - t1) * 1000), end='\t')
    print()

if __name__ == '__main__':
    for list_size in [10, 1000, 2000, 3000, 4000, 5000, 10000]:
        L = list(range(list_size))
        random.shuffle(L)
        printTimes(L)

入出力結果(Terminal, IPython)

$ ./sample7.py
10     0.1     0.1     0.1     0.0 
1000   526.4   228.2   687.8     1.0 
2000  2038.0   927.2  2807.4     2.2 
3000  4627.1  2109.8  6325.3     3.4 
4000  8229.8  3795.4 11312.3     4.7 
5000 13103.3  5894.8 17911.9     6.0 
10000 66105.8 27104.1 72529.2    13.2 
$