バブルソート

Python

昨日二分探索はソートが完了していることが前提条件と言っていたので、今日はソートかな。
バブルソート。
泡がボコボコッと水面に上昇していくように、大きな数字がどんどん後ろにずれてゆく。
すんごい単純なアルゴリズム。
Pythonだとsort()という関数があるので別に必要ないっちゃないんだけど確認のため。


インスパイヤ先↓
http://f59.aaa.livedoor.jp/~ookini/pukiwiki.php?bubsort.py

# Bubble Sort

import random
import time

def bubble(numList):
    for i in range(len(numList)):
        for j in range(i+1, len(numList)):
            if numList[i] > numList[j]:
                tmp = numList[i]
                numList[i] = numList[j]
                numList[j] = tmp


def main():
    N = 20
    numList = [random.randint(1,100) for i in range(N)]
    print numList

    start = time.clock()
    bubble(numList)
    finish = time.clock()

    print numList
    print finish-start

if __name__ == "__main__":
    main()

要素がランダムなリストを生成し、バブルソートを行う。
結果がこちら

D:\workspace\Python>python sort.py
[45, 18, 89, 18, 54, 17, 4, 86, 98, 46, 49, 68, 18, 29, 28, 28, 18, 95, 97, 51]
[4, 17, 18, 18, 18, 18, 28, 28, 29, 45, 46, 49, 51, 54, 68, 86, 89, 95, 97, 98]
7.66424565044e-005

比較対象がないので早いかどうかは不明。
計算量はリストの要素数をxとするとO(x^2)だったはず。
理由は長さxの２重ループがあるから。