2

バブルと挿入ソートのタイミングを計ろうとしています。並べ替えは両方とも正常に機能しますが、15 秒かかると出力されますが、これは明らかに正しくありません。これを修正する方法はありますか？

# insertion sort
x = [7, 2, 3, 5, 9, 1]

def insertion(list):
    for index in range(1,len(list)):
        value = list[index]
        i = index - 1
        while i>=0 and (value < list[i]):
            list[i+1] = list[i] # shift number in slot i right to slot i+1
            list[i] = value # shift value left into slot i
            i = i - 1

# bubble sort
y = [7, 2, 3, 5, 9, 1]

def bubble(unsorted_list):
    length = len(unsorted_list) - 1
    sorted = False

    while not sorted:
        sorted = True
        for i in range(length):
            if unsorted_list[i] > unsorted_list[i+1]:
                sorted = False
                unsorted_list[i], unsorted_list[i+1] = unsorted_list[i+1], unsorted_list[i]

def test():
    bubble(y)
    insertion(x)

if __name__ == '__main__':
    import timeit
    print(timeit.timeit("test()", setup="from __main__ import test"))
4

3 に答える 3

5

timeitドキュメントから：

timeit.timeit (stmt='pass', setup='pass', timer=, number=1000000)

指定されたステートメント、セットアップ コード、およびタイマー関数を使用して Timer インスタンスを作成し、その timeit() メソッドを実行回数を指定して実行します。

したがって、コードは 1,000,000 回実行されます。戻り値を10**6で割ります。

于 2013-04-11T19:47:08.403 に答える
-1

これを試してみてください。現在の時間をキャプチャし、関数を実行してから、以前にキャプチャした時間を現在の時間から減算します。

# insertion sort
x = [7, 2, 3, 5, 9, 1]

def insertion(list):
    for index in range(1,len(list)):
        value = list[index]
        i = index - 1
        while i>=0 and (value < list[i]):
            list[i+1] = list[i] # shift number in slot i right to slot i+1
            list[i] = value # shift value left into slot i
            i = i - 1

# bubble sort
y = [7, 2, 3, 5, 9, 1]

def bubble(unsorted_list):
    length = len(unsorted_list) - 1
    sorted = False

    while not sorted:
        sorted = True
        for i in range(length):
            if unsorted_list[i] > unsorted_list[i+1]:
                sorted = False
                unsorted_list[i], unsorted_list[i+1] = unsorted_list[i+1], unsorted_list[i]

def test():
    start = time.clock()
    bubble(y)
    elapsed = (time.clock() - start)
    print "Time taken for bubble = ", elapsed
    start = time.clock()
    insertion(x)
    elapsed = (time.clock() - start)
    print "Time taken for Insertion = ", elapsed

if __name__ == '__main__':
    import time
    test()
于 2013-04-11T19:48:58.910 に答える