ソートアルゴリズム入門 - バブルソート編 -

はじめに

pythonの習得を兼ねて、ソートアルゴリズムを実装していきます。
他に効率的な書き方があれば、教えて下さい。

実行時間測定

定数	説明	値
N	要素数	10000個
LOOP	実行回数	10回

main.py

import numpy as np
import time

# sort algorithm
from bubble import sort

N = 10000
LOOP = 10
exe_times = []
arr = range(N)

for i in range(LOOP):
    np.random.shuffle(arr)
    start = time.time()

    # ソートアルゴリズム
    sort(arr)

    exe_time = time.time() - start
    exe_times.append(exe_time)

for i in range(LOOP):
    bad_array = sorted(arr, reverse=True)
    start = time.time()

    # ソートアルゴリズム
    sort(bad_array)

    exe_time = time.time() - start
    exe_times.append(exe_time)

for i in range(LOOP):
    good_array = sorted(arr)
    start = time.time()

    # ソートアルゴリズム
    sort(good_array)

    exe_time = time.time() - start
    exe_times.append(exe_time)

print("Average: {0}{1}".format(np.average(exe_times), "[sec]"))
print("Max: {0}{1}".format(np.max(exe_times), "[sec]"))
print("Min: {0}{1}".format(np.min(exe_times), "[sec]"))

バブルソート

bubble.py

def sort(array):
    length = len(array)
    while True:
        swapped = False
        for i in xrange(length-1):
            if array[i] > array[i+1]:
                array[i], array[i+1] = array[i+1], array[i]
                swapped = True
        length -= 1
        if not swapped:
            break
    return array

実行結果

Average: 5.69646668434[sec]
Max: 10.6949999332[sec]
Min: 0.0[sec]