Python バブルソート

バブル ソート アルゴリズムは、隣接する要素の各ペアを比較し、順序が揃っていない場合は要素を交換する比較ベースのアルゴリズムです。バブル ソートの平均および最悪の場合の複雑さは O(n2) です (n は項目の数)。

Python bubble sort examples

  • Example 1 - basic
# ascending order:
In [1]: x = [7,2,8,9,4,3,5,6,1]

In [2]: print x
[7, 2, 8, 9, 4, 3, 5, 6, 1]

In [3]: for i in range(len(x)):
   ...:     for j in range(len(x)-1-i):
   ...:         if x[j] > x[j+1]:
   ...:             x[j], x[j+1] = x[j+1], x[j]
   ...:             

In [4]: print x
[1, 2, 3, 4, 5, 6, 7, 8, 9]

# descending order:
In [5]: x = [7,2,8,9,4,3,5,6,1]

In [6]: print x
[7, 2, 8, 9, 4, 3, 5, 6, 1]

In [7]: for i in range(len(x)):
   ...:     for j in range(len(x)-1-i):
   ...:         if x[j] < x[j+1]:
   ...:             x[j], x[j+1] = x[j+1], x[j]
   ...:             

In [8]: print x
[9, 8, 7, 6, 5, 4, 3, 2, 1]
  • Example 2 - improved
In [1]: x = [6,1,2,3,4,5]

In [2]: for i in range(len(x)):
   ...:     sorted = True
   ...:     for j in range(len(x)-1-i):
   ...:         if x[j] > x[j+1]:
   ...:             x[j], x[j+1] = x[j+1], x[j]
   ...:             sorted = False
   ...:     if sorted:
   ...:         break
   ...:     

In [3]: print x
[1, 2, 3, 4, 5, 6]

参考文献

python algorithm

🇨🇳 🇯🇵 📍 ⌚