バブルソート

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

Miriam Antona

Software engineer

ソートアルゴリズム

{{1}} を深く学ぶ
未整列の集合を昇順/降順に並べ替える方法を解く
問題の複雑さを減らせることがある
代表的なソート:
- bubble sort
- selection sort
- insertion sort
- merge sort
- quicksort

バブルソート

未整列の数値リストの模式図。1番目と2番目の要素を指す2つのポインタがある。

1つ目 > 2つ目

バブルソート

未整列の数値リストの模式図。1番目と2番目の要素を指す2つのポインタがあり、1番目と2番目が入れ替わっている。

1つ目 > 2つ目
- 交換
2つ目 > 1つ目
- 何もしない

バブルソート

未整列の数値リストの模式図。2番目と3番目の要素を指す2つのポインタがある。

1つ目 > 2つ目
- 交換
2つ目 > 1つ目
- 何もしない

バブルソート

未整列の数値リストの模式図。3番目と4番目の要素を指す2つのポインタがある。

1つ目 > 2つ目
- 交換
2つ目 > 1つ目
- 何もしない

バブルソート

未整列の数値リストの模式図。3番目の要素と4番目の要素を指す2つのポインタがあり、3番目と4番目が入れ替わっている。

1つ目 > 2つ目
- 交換
2つ目 > 1つ目
- 何もしない

バブルソート

未整列の数値リストの模式図。4番目と5番目の要素を指す2つのポインタがある。

1つ目 > 2つ目
- 交換
2つ目 > 1つ目
- 何もしない

バブルソート

未整列の数値リストの模式図。4番目と5番目の要素を指す2つのポインタがあり、4番目と5番目が入れ替わっている。

1つ目 > 2つ目
- 交換
2つ目 > 1つ目
- 何もしない

バブルソート

未整列の数値リストの模式図。4番目と5番目の要素を指す2つのポインタがあり、5番目は整列済みとして青色。

1つ目 > 2つ目
- 交換
2つ目 > 1つ目
- 何もしない

バブルソート

未整列の数値リストの模式図。1番目と2番目の要素を指す2つのポインタがあり、最後の要素は青色。

1つ目 > 2つ目
- 交換
2つ目 > 1つ目
- 何もしない

バブルソート

未整列の数値リストの模式図。2番目と3番目の要素を指す2つのポインタがあり、最後の要素は青色。

1つ目 > 2つ目
- 交換
2つ目 > 1つ目
- 何もしない

バブルソート

未整列の数値リストの模式図。2番目と3番目の要素を指す2つのポインタがあり、2番目と3番目が入れ替わっている。最後の要素は青色。

1つ目 > 2つ目
- 交換
2つ目 > 1つ目
- 何もしない

バブルソート

未整列の数値リストの模式図。3番目と4番目の要素を指す2つのポインタがあり、最後の要素は青色。

1つ目 > 2つ目
- 交換
2つ目 > 1つ目
- 何もしない

バブルソート

未整列の数値リストの模式図。3番目と4番目の要素を指す2つのポインタがあり、最後の2要素は青色。

1つ目 > 2つ目
- 交換
2つ目 > 1つ目
- 何もしない

バブルソート

未整列の数値リストの模式図。1番目と2番目の要素を指す2つのポインタがあり、最後の2要素は青色。

1つ目 > 2つ目
- 交換
2つ目 > 1つ目
- 何もしない

バブルソート

未整列の数値リストの模式図。1番目と2番目の要素を指す2つのポインタがあり、1番目と2番目が入れ替わっている。最後の2要素は青色。

1つ目 > 2つ目
- 交換
2つ目 > 1つ目
- 何もしない

バブルソート

未整列の数値リストの模式図。2番目と3番目の要素を指す2つのポインタがあり、最後の2要素は青色。

1つ目 > 2つ目
- 交換
2つ目 > 1つ目
- 何もしない

バブルソート

未整列の数値リストの模式図。2番目と3番目の要素を指す2つのポインタがあり、最後の3要素は青色。

1つ目 > 2つ目
- 交換
2つ目 > 1つ目
- 何もしない

バブルソート

未整列の数値リストの模式図。1番目と2番目の要素を指す2つのポインタがあり、最後の3要素は青色。

1つ目 > 2つ目
- 交換
2つ目 > 1つ目
- 何もしない

バブルソート

未整列の数値リストの模式図。1番目と2番目の要素を指す2つのポインタがあり、最後の4要素は青色。

1つ目 > 2つ目
- 交換
2つ目 > 1つ目
- 何もしない

バブルソート

未整列の数値リストの模式図。1番目と2番目の要素を指す2つのポインタがあり、すべての要素が青色。

1つ目 > 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で学ぶデータ構造とアルゴリズム