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-6.を解いてみる。

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

長さNのリストについて。

ソート済の場合

ソート方法	比較回数	コピー回数
選択ソート	N(N - 1) / 2	2N
挿入ソート	N - 1	2N

逆順の場合(降順の場合)

ソート方法	比較回数	コピー回数
選択ソート	N(N - 1) /2	2N
挿入ソート	N(N - 1) / 2	2N

全ての値が同じ場合

ソート方法	比較回数	コピー回数
選択ソート	N(N - 1) / 2	2N
挿入ソート	N(N - 1) / 2	2N

N = 10の場合で確認。

コード(BBEdit)

sample.py

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

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

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

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

def insert(l, b, cmp, cp):
    i = b
    while i != 0:
        cmp += 1
        if l[i- 1] >= l[b]:
            i -= 1
        else:
            break
    v = l.pop(b)
    l.insert(i, v)
    cp += 2
    return (cmp, cp)

if __name__ == '__main__':
    n = 10
    l = list(range(n))
    for f in [selectionSort, insertionSort]:
        print(f.__name__)
        for x in [l, sorted(l, reverse=True), [0] * n]:
            cmp, cp = f(x)
            print('比較: {0:2} コピー: {1}'.format(cmp, cp))

入出力結果(Terminal)

$ ./sample.py
selectionSort
比較: 45 コピー: 20
比較: 45 コピー: 20
比較: 45 コピー: 20
insertionSort
比較:  9 コピー: 20
比較: 45 コピー: 20
比較: 45 コピー: 20
$