【アルゴリズムの勉強】Pythonでバブルソートを書いてみた

学習エントリ。

Pythonでバブルソートを実装する。

バブルソートってなんぞ

ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。安定な内部ソート。基本交換法、隣接交換法ともいう。（単に交換法と言う場合もある）

バブルソート - Wikipedia

example_list = [4,2,5,1,18,3]
ASC, DESC = 1, 2

def bubleSort(list,order):
    while True:
        continue_flg = 0
        if order == ASC:
            for i in xrange(len(list) - 1):
                if list[i] > list[i + 1]:
                    list[i], list[i + 1] = list[i + 1], list[i]
                    continue_flg = 1 
        elif order == DESC:
            for i in xrange(len(list) - 1):
                if list[i] < list[i + 1]:
                    list[i], list[i + 1] = list[i + 1], list[i]
                    continue_flg = 1 
        if continue_flg == 0:
            return list


#result
print("ASC is...")
print(bubleSort(example_list,ASC)) #[1, 2, 3, 4, 5, 18]
print("DESC is...")
print(bubleSort(example_list,DESC)) #[18, 5, 4, 3, 2, 1]

• スワップが容易だった
• while Trueで永続的にループ。flgの値で処理を抜けるか判定。
• for文内の条件式に入っていない→flgが更新されていない→必要な処理は終わったと判断し、抜ける。
• もっと効率的な方法を模索