バブルソート

Pythonで学ぶデータ構造とアルゴリズム

Miriam Antona

Software engineer

ソートアルゴリズム

深く研究されてきたテーマ
ランダムな順序のデータを昇順/降順に並び替えるためのもの
問題解決の効率が大幅に向上
代表的なソートアルゴリズム：
- バブルソート
- 選択ソート
- 挿入ソート
- マージソート
- クイックソート

バブルソート

順不同の番号が並んだリスト。最初の要素を指すポインターがあり、2番目の要素を指す別のポインターがある。

最初の値が2番目の値より大きい

バブルソート

順不同の番号が並んだリスト。 1つのポインタが最初の要素を指し、別のポインタが2番目の要素を指している。最初の要素と2番目の要素が入れ替わっている。

最初の値が2番目の値より大きい
- 入れ替える
2番目の値が1番目の値より大きい
- 何もしない

バブルソート

順不同の番号が並んだリスト。 2番目の要素を指すポインターがあり、3番目の要素を指す別のポインターがある。

最初の値が2番目の値より大きい
- 入れ替える
2番目の値が1番目の値より大きい
- 何もしない

バブルソート

順不同の番号が並んだリスト。 3番目の要素を指すポインターがあり、4番目の要素を指す別のポインターがある。

最初の値が2番目の値より大きい
- 入れ替える
2番目の値が1番目の値より大きい
- 何もしない

バブルソート

順不同の番号が並んだリスト。 3番目の要素を指すポインタがあり、4番目の要素を指す別のポインタがある。 3番目と4番目の要素が入れ替わる。

最初の値が2番目の値より大きい
- 入れ替える
2番目の値が1番目の値より大きい
- 何もしない

バブルソート

順不同の番号が並んだリスト。 4番目の要素を指すポインターがあり、別のポインターが5番目の要素を指している。

最初の値が2番目の値より大きい
- 入れ替える
2番目の値が1番目の値より大きい
- 何もしない

バブルソート

順不同の番号が並んだリスト。 4番目の要素を指すポインタがあり、5番目の要素を指す別のポインタがある。 4番目と5番目の要素が入れ替わっている。

最初の値が2番目の値より大きい
- 入れ替える
2番目の値が1番目の値より大きい
- 何もしない

バブルソート

順不同の番号が並んだリスト。 4番目の要素を指すポインタがあり、5番目の要素を指す別のポインタがある。 5番目の要素は、順序があるため青色で表示されている。

最初の値が2番目の値より大きい
- 入れ替える
2番目の値が1番目の値より大きい
- 何もしない

バブルソート

順不同の番号が並んだリスト。 1つのポインタが最初の要素を指し、別のポインタが2番目の要素を指している。最後の要素は青色で表示されている。

最初の値が2番目の値より大きい
- 入れ替える
2番目の値が1番目の値より大きい
- 何もしない

バブルソート

順不同の番号が並んだリスト。 2番目の要素を指すポインタがあり、3番目の要素を指す別のポインタがある。最後の要素は青色で表示されている。

最初の値が2番目の値より大きい
- 入れ替える
2番目の値が1番目の値より大きい
- 何もしない

バブルソート

順不同の番号が並んだリスト。 2番目の要素を指すポインタがあり、3番目の要素を指す別のポインタがある。 2番目と3番目の要素が入れ替わっている。最後の要素は青色で表示されている。

最初の値が2番目の値より大きい
- 入れ替える
2番目の値が1番目の値より大きい
- 何もしない

バブルソート

順不同の番号が並んだリスト。 3番目の要素を指すポインタがあり、4番目の要素を指す別のポインタがある。最後の要素は青色で表示されている。

最初の値が2番目の値より大きい
- 入れ替える
2番目の値が1番目の値より大きい
- 何もしない

バブルソート

順不同の番号が並んだリスト。 3番目の要素を指すポインタがあり、4番目の要素を指す別のポインタがある。最後の2つの要素は青色で表示されている。

最初の値が2番目の値より大きい
- 入れ替える
2番目の値が1番目の値より大きい
- 何もしない

バブルソート

順不同の番号が並んだリスト。 1つのポインタが最初の要素を指し、別のポインタが2番目の要素を指している。最後の2つの要素は青色で表示されている。

最初の値が2番目の値より大きい
- 入れ替える
2番目の値が1番目の値より大きい
- 何もしない

バブルソート

順不同の番号が並んだリスト。 1つのポインタが最初の要素を指し、別のポインタが2番目の要素を指している。最初の要素と2番目の要素が入れ替わっている。最後の2つの要素は青色で表示されている。

最初の値が2番目の値より大きい
- 入れ替える
2番目の値が1番目の値より大きい
- 何もしない

バブルソート

順不同の番号が並んだリスト。 2番目の要素を指すポインタがあり、3番目の要素を指す別のポインタがある。最後の2つの要素は青色で表示されている。

最初の値が2番目の値より大きい
- 入れ替える
2番目の値が1番目の値より大きい
- 何もしない

バブルソート

順不同の番号が並んだリスト。 2番目の要素を指すポインタがあり、3番目の要素を指す別のポインタがある。最後の3つの要素は青色で表示されている。

最初の値が2番目の値より大きい
- 入れ替える
2番目の値が1番目の値より大きい
- 何もしない

バブルソート

順不同の番号が並んだリスト。 1つのポインタが最初の要素を指し、別のポインタが2番目の要素を指している。最後の3つの要素は青色で表示されている。

最初の値が2番目の値より大きい
- 入れ替える
2番目の値が1番目の値より大きい
- 何もしない

バブルソート

順不同の番号が並んだリスト。 1つのポインタが最初の要素を指し、別のポインタが2番目の要素を指している。最後の4つの要素は青色で表示されている。

最初の値が2番目の値より大きい
- 入れ替える
2番目の値が1番目の値より大きい
- 何もしない

バブルソート

順不同の番号が並んだリスト。 1つのポインタが最初の要素を指し、別のポインタが2番目の要素を指している。すべての要素は青色で表示されている。

最初の値が2番目の値より大きい
- 入れ替える
2番目の値が1番目の値より大きい
- 何もしない

バブルソート - 実装

def bubble_sort(my_list):
  list_length = len(my_list)
  for i in range(list_length-1):
    for j in range(list_length-1-i):

      if my_list[j] > my_list[j+1]:

        my_list[j] , my_list[j+1] = my_list[j+1] , my_list[j]

  return my_list

print(bubble_sort([4,3,7,1,5]))

[1, 3, 4, 5, 7]

バブルソート - 実装

def bubble_sort(my_list):
  list_length = len(my_list)
  is_sorted = False

  while not is_sorted:

    is_sorted = True

    for i in range(list_length-1):

      if my_list[i] > my_list[i+1]:

        my_list[i] , my_list[i+1] = my_list[i+1] , my_list[i]

        is_sorted = False

    list_length -= 1

  return my_list

バブルソート - 計算量

最悪：$O(n^2)$
最良 - 未改良版：$\Omega(n^2)$
最良 - 改良版：$\Omega(n)$
平均：$\Theta(n^2)$
大規模で無秩序なリストではあまり効率的ではない
優れたパフォーマンス：
- ソート済み／ほぼソート済みの大規模リスト
- 小さなリスト

練習しましょう！

Pythonで学ぶデータ構造とアルゴリズム