選択ソートと挿入ソート

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

Miriam Antona

Software engineer

選択ソート

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

最小値を判定する

選択ソート

順不同の番号が並んだリスト。最初の要素を指すポインタがある。最初の要素はオレンジ色で表示されている。

最小値を判定する

選択ソート

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

最小値を判定する

選択ソート

順不同の番号が並んだリスト。 2番目の要素を指すポインタが1つある。 2つ目の要素はオレンジ色。

最小値を判定する

選択ソート

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

最小値を判定する

選択ソート

順不同の番号が並んだリスト。 4番目の要素を指すポインターがある。 2つ目の要素はオレンジ色で表示されている。

最小値を判定する

選択ソート

順不同の番号が並んだリスト。 4番目の要素を指すポインターがある。 4番目の要素はオレンジ色で表示されている。

最小値を判定する

選択ソート

順不同の番号が並んだリスト。 5番目の要素を指すポインタがある。 4番目の要素はオレンジ色で表示されている。

最小値を判定する

選択ソート

順不同の番号が並んだリスト。 4番目の要素はオレンジ色で表示されている。最初の要素と4番目の要素が入れ替わることを示す2本の矢印がある。

最小値を判定する
最小値をまだ並び替えていない先頭の値と交換

選択ソート

順不同の番号が並んだリスト。最初の要素はオレンジ色で表示されている。最初の要素と4番目の要素が入れ替わっている。

最小値を判定する
最小値をまだ並び替えていない先頭の値と交換

選択ソート

順不同の番号が並んだリスト。最初の要素は青色で、2番目の要素はオレンジ色。 2番目の要素を指すポインタがある。

最小値を判定する
最小値をまだ並び替えていない先頭の値と交換

選択ソート

順不同の番号が並んだリスト。最初の要素は青色で、2番目の要素はオレンジ色。 3番目の要素を指すポインタがある

最小値を判定する
最小値をまだ並び替えていない先頭の値と交換

選択ソート

順不同の番号が並んだリスト。最初の要素は青色で、2番目の要素はオレンジ色。 4番目の要素を指すポインタがある。

最小値を判定する
最小値をまだ並び替えていない先頭の値と交換

選択ソート

順不同の番号が並んだリスト。最初の要素は青色で、2番目の要素はオレンジ色。 5番目の要素を指すポインタがある。

最小値を判定する
最小値をまだ並び替えていない先頭の値と交換

選択ソート

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

最小値を判定する
最小値をまだ並び替えていない先頭の値と交換

選択ソート

順不同の番号が並んだリスト。最初と2番目の要素は青色で、3番目の要素はオレンジ色。 3番目の要素を指すポインタがある。

最小値を判定する
最小値をまだ並び替えていない先頭の値と交換

選択ソート

順不同の番号が並んだリスト。最初と2番目の要素は青色で、3番目の要素はオレンジ色。 4番目の要素を指すポインターがある。

最小値を判定する
最小値をまだ並び替えていない先頭の値と交換

選択ソート

順不同の番号が並んだリスト。最初と2番目の要素は青色で、4番目の要素はオレンジ色。 4番目の要素を指すポインタがある。

最小値を判定する
最小値をまだ並び替えていない先頭の値と交換

選択ソート

順不同の番号が並んだリスト。最初と2番目の要素は青色で、4番目の要素はオレンジ色。 5番目の要素を指すポインタがある。

最小値を判定する
最小値をまだ並び替えていない先頭の値と交換

選択ソート

順不同の番号が並んだリスト。最初と2番目の要素は青色で、4番目の要素はオレンジ色。 3番目と4番目の項目が入れ替わることを示す2本の矢印がある。

最小値を判定する
最小値をまだ並び替えていない先頭の値と交換

選択ソート

順不同の番号が並んだリスト。最初と2番目の要素は青色で、3番目の要素はオレンジ色。 3番目と4番目の項目が入れ替わっている。

最小値を判定する
最小値をまだ並び替えていない先頭の値と交換

選択ソート

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

最小値を判定する
最小値をまだ並び替えていない先頭の値と交換

選択ソート

順不同の番号が並んだリスト。最初、2番目、3番目の要素は青色で、4番目の要素はオレンジ色。 4番目の要素を指すポインタがある。

最小値を判定する
最小値をまだ並び替えていない先頭の値と交換

選択ソート

順不同の番号が並んだリスト。最初、2番目、3番目の要素は青色で、4番目の要素はオレンジ色。 5番目の要素を指すポインタがある。

最小値を判定する
最小値をまだ並び替えていない先頭の値と交換

選択ソート

順不同の番号が並んだリスト。最初、2番目、3番目の要素は青色で、5番目の要素はオレンジ色。 5番目の要素を指すポインターがある。

最小値を判定する
最小値をまだ並び替えていない先頭の値と交換

選択ソート

順不同の番号が並んだリスト。最初、2番目、3番目の要素は青色で、5番目の要素はオレンジ色。 4番目と5番目の要素が入れ替わることを示す2本の矢印がある。

最小値を判定する
最小値をまだ並び替えていない先頭の値と交換

選択ソート

順不同の番号が並んだリスト。最初、2番目、3番目の要素は青色で、4番目の要素はオレンジ色。 4番目と5番目の要素が入れ替わっている。

最小値を判定する
最小値をまだ並び替えていない先頭の値と交換

選択ソート

順不同の番号が並んだリスト。最初、2番目、3番目、4番目の要素は青色で表示されている。

最小値を判定する
最小値をまだ並び替えていない先頭の値と交換

選択ソート

順不同の番号が並んだリスト。すべての要素は青色で表示されている。

最小値を判定する
最小値をまだ並び替えていない先頭の値と交換

選択ソート - 実装

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

    lowest = my_list[i]

    index = i

    for j in range(i + 1, list_length):

      if my_list[j] < lowest:

        index = j

        lowest = my_list[j]

    my_list[i] , my_list[index] = my_list[index] , my_list[i]

  return my_list

選択ソート - 計算量

最悪：$O(n^2)$
平均：$\Theta(n^2)$
最良：$\Omega(n^2)$

挿入ソート

順不同の番号が並んだリスト。

挿入ソート

順不同の番号が並んだリスト。最初の要素は青色で、2番目の要素は他の要素より上に移動されている。

挿入ソート

順不同の番号が並んだリスト。最初の要素は青色で表示され、2番目の要素は他の要素より上に配置されている。最初の要素が右に移動している。

挿入ソート

順不同の番号が並んだリスト。 2つ目の要素は青色で表示されている。押し上げられた要素は現在、最初の位置にある。

挿入ソート

順不同の番号が並んだリスト。最初と2番目の要素は青色で表示されている。

挿入ソート

順不同の番号が並んだリスト。最初の要素と2番目の要素は青色で表示されている。 3番目の要素が他の要素より上に移動している。

挿入ソート

順不同の番号が並んだリスト。最初、2番目、3番目の要素は青色で表示されている。

挿入ソート

順不同の番号が並んだリスト。最初、2番目、3番目の要素は青色で表示されている。 3番目の要素が他の要素より上に移動している。

挿入ソート

順不同の番号が並んだリスト。最初、2番目、3番目の要素は青色で表示されている。 3つ目の要素は、他の要素より上に配置されている。 3番目の要素が右に移動している。

挿入ソート

順不同の番号が並んだリスト。最初、2番目、3番目の要素は青色で表示されている。 3つ目の要素は、他の要素より上に配置されている。 3番目と2番目の要素が右に移動している。

挿入ソート

順不同の番号が並んだリスト。最初、2番目、3番目の要素は青色で表示されている。 3つ目の要素は、他の要素より上に配置されている。 3番目、2番目、3番目の要素が右にシフトされている。

挿入ソート

順不同の番号が並んだリスト。最初、2番目、3番目の要素は青色で表示されている。 3つ目の要素は、他の要素より上に配置されている。 3番目、2番目、3番目の要素が右に移動している。昇格された要素が、現在は最初の位置にある。

挿入ソート

順不同の番号が並んだリスト。最初、2番目、3番目、4番目の要素は青色で表示されている。

挿入ソート

順不同の番号が並んだリスト。最初、2番目、3番目、4番目の要素は青色で表示されている。 5番目の要素が他の要素より上に移動している。

挿入ソート

順不同の番号が並んだリスト。最初、2番目、3番目、4番目の要素は青色で表示されている。 5番目の要素は他の要素より上に配置されている。 4番目の要素が右に移動している。

挿入ソート

順不同の番号が並んだリスト。最初、2番目、3番目、4番目の要素は青色で表示されている。 5番目の要素は他の要素より上に配置されている。昇格した要素は現在4番目の位置にある。

挿入ソート - 実装

def insertion_sort(my_list):
  for i in range(1, len(my_list)):

      number_to_order = my_list[i]

      j = i - 1

      while j >= 0 and number_to_order < my_list[j]:

          my_list[j + 1] = my_list[j]

          j -= 1

      my_list[j + 1] = number_to_order

  return my_list

挿入ソート - 計算量

最悪：$O(n^2)$
平均：$\Theta(n^2)$
最良：$\Omega(n)$

練習しましょう！

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