Bubble sortがO(n^2)を体感した話。

やったこと

bubble sortをpythonで実装して、ソートするリストの長さを変え、実行時間がリストの長さの２乗に比例することを理解した。

実装

https://qiita.com/shinshin86/items/40122455dee2bfd2f3f1
を参考にして、ランダムな配列の作り方を実装しました。

長さeのランダムな並びのリストを作って、それぞれに対して、実行時間を測っています。

bubble_sort.py

def bubble_sort(a):
    # input array and return sorted array
    for i in range(1,len(a)):
        j = i # j is current pos
        while j != 0 and a[j] < a[j-1]:
            a[j],a[j-1] = a[j-1],a[j]
            j -= 1
    return a 


e=[10,100,1000,10000,100000] # 要素数
size = 1000000 # 0~sizeまで
if __name__=="__main__":
    import random
    import time
    for k in e:
        init_list = random. sample(list(range(0, size)), k)
        #print(init_list)

        start = time.time()
        bubble_sort(init_list)
        end = time.time()

        #print(init_list)
        print("bubble_sort : size {} time {}".format(k,end-start))

　結果

bubble_sort : size 10 time 1.9311904907226562e-05
bubble_sort : size 100 time 0.0008120536804199219
bubble_sort : size 1000 time 0.07604408264160156
bubble_sort : size 10000 time 7.907392978668213

sizeが１０の時に小さいのは、ソート以外での処理にかかる時間（関数の呼び出しなど？）と思えば、リスト長が大きくなると、size100から1000,1000から１００００をみると、長さが１０倍になると、実行時間が100倍になっていることがわかります。

　余談（逆順にソートされている場合）

reverse_list.py

def bubble_sort(a):
    # input array and return sorted array
    for i in range(1,len(a)):
        j = i # j is current pos
        while j != 0 and a[j] < a[j-1]:
            a[j],a[j-1] = a[j-1],a[j]
            j -= 1
    return a 


e=[10,100,1000,10000,100000] # 要素数
size = 1000000 # 0~sizeまで
if __name__=="__main__":
    import random
    import time
    for k in e:
        #init_list = list(range(k,0,-1))
        init_list = random. sample(list(range(0, size)), k)
        if k < 100:
            print(init_list)
        pass
        start = time.time()
        bubble_sort(init_list)
        end = time.time()

        #print(init_list)
        print("bubble_sort : size {} time {}".format(k,end-start))

ちなみに逆順になっている場合は、理論的には、単純に、一番外のループ（今回のコードでいうところでのi)で、終了するまでにswapを繰り返す回数(jを何回更新するか）が、ランダムな時は、i/2で理論的になるのが、逆順になっている場合は、全部入れ替える必要があるので、i回swapが必要となり、ループを回る回数（実行時間も）は2倍になるはずです。（あってますよね？）

そこで実行してみると、以下のようになり、確かに、ランダムな場合の２倍かかっていることが確認できました。
面白いですね。

[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
bubble_sort : size 10 time 1.5020370483398438e-05
bubble_sort : size 100 time 0.001268148422241211
bubble_sort : size 1000 time 0.15845394134521484
bubble_sort : size 10000 time 14.583886861801147