選択ソートと挿入ソート

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

Miriam Antona

Software engineer

選択ソート

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

  • 最小値を見つける
Pythonで学ぶデータ構造とアルゴリズム

選択ソート

未整列の数値リストの模式図。1番目の要素を指すポインタが1つ。1番目の要素がオレンジ色。

  • 最小値を見つける
Pythonで学ぶデータ構造とアルゴリズム

選択ソート

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

  • 最小値を見つける
Pythonで学ぶデータ構造とアルゴリズム

選択ソート

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

  • 最小値を見つける
Pythonで学ぶデータ構造とアルゴリズム

選択ソート

未整列の数値リストの模式図。3番目の要素を指すポインタが1つ。2番目の要素がオレンジ色。

  • 最小値を見つける
Pythonで学ぶデータ構造とアルゴリズム

選択ソート

未整列の数値リストの模式図。4番目の要素を指すポインタが1つ。2番目の要素がオレンジ色。

  • 最小値を見つける
Pythonで学ぶデータ構造とアルゴリズム

選択ソート

未整列の数値リストの模式図。4番目の要素を指すポインタが1つ。4番目の要素がオレンジ色。

  • 最小値を見つける
Pythonで学ぶデータ構造とアルゴリズム

選択ソート

未整列の数値リストの模式図。5番目の要素を指すポインタが1つ。4番目の要素がオレンジ色。

  • 最小値を見つける
Pythonで学ぶデータ構造とアルゴリズム

選択ソート

未整列の数値リストの模式図。4番目の要素がオレンジ色。1番目と4番目の要素を入れ替える矢印が2つ。

  • 最小値を見つける
  • 最小値を未整列の先頭と交換
Pythonで学ぶデータ構造とアルゴリズム

選択ソート

未整列の数値リストの模式図。1番目がオレンジ色。1番目と4番目が入れ替わっている。

  • 最小値を見つける
  • 最小値を未整列の先頭と交換
Pythonで学ぶデータ構造とアルゴリズム

選択ソート

未整列の数値リストの模式図。1番目が青、2番目がオレンジ。2番目を指すポインタが1つ。

  • 最小値を見つける
  • 最小値を未整列の先頭と交換
Pythonで学ぶデータ構造とアルゴリズム

選択ソート

未整列の数値リストの模式図。1番目が青、2番目がオレンジ。3番目を指すポインタが1つ。

  • 最小値を見つける
  • 最小値を未整列の先頭と交換
Pythonで学ぶデータ構造とアルゴリズム

選択ソート

未整列の数値リストの模式図。1番目が青、2番目がオレンジ。4番目を指すポインタが1つ。

  • 最小値を見つける
  • 最小値を未整列の先頭と交換
Pythonで学ぶデータ構造とアルゴリズム

選択ソート

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

  • 最小値を見つける
  • 最小値を未整列の先頭と交換
Pythonで学ぶデータ構造とアルゴリズム

選択ソート

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

  • 最小値を見つける
  • 最小値を未整列の先頭と交換
Pythonで学ぶデータ構造とアルゴリズム

選択ソート

未整列の数値リストの模式図。1番目と2番目が青、3番目がオレンジ。3番目を指すポインタが1つ。

  • 最小値を見つける
  • 最小値を未整列の先頭と交換
Pythonで学ぶデータ構造とアルゴリズム

選択ソート

未整列の数値リストの模式図。1番目と2番目が青、3番目がオレンジ。4番目を指すポインタが1つ。

  • 最小値を見つける
  • 最小値を未整列の先頭と交換
Pythonで学ぶデータ構造とアルゴリズム

選択ソート

未整列の数値リストの模式図。1番目と2番目が青、4番目がオレンジ。4番目を指すポインタが1つ。

  • 最小値を見つける
  • 最小値を未整列の先頭と交換
Pythonで学ぶデータ構造とアルゴリズム

選択ソート

未整列の数値リストの模式図。1番目と2番目が青、4番目がオレンジ。5番目を指すポインタが1つ。

  • 最小値を見つける
  • 最小値を未整列の先頭と交換
Pythonで学ぶデータ構造とアルゴリズム

選択ソート

未整列の数値リストの模式図。1番目と2番目が青、4番目がオレンジ。3番目と4番目を入れ替える矢印が2つ。

  • 最小値を見つける
  • 最小値を未整列の先頭と交換
Pythonで学ぶデータ構造とアルゴリズム

選択ソート

未整列の数値リストの模式図。1番目と2番目が青、3番目がオレンジ。3番目と4番目が入れ替わっている。

  • 最小値を見つける
  • 最小値を未整列の先頭と交換
Pythonで学ぶデータ構造とアルゴリズム

選択ソート

未整列の数値リストの模式図。1〜3番目が青。4番目を指すポインタが1つ。

  • 最小値を見つける
  • 最小値を未整列の先頭と交換
Pythonで学ぶデータ構造とアルゴリズム

選択ソート

未整列の数値リストの模式図。1〜3番目が青、4番目がオレンジ。4番目を指すポインタが1つ。

  • 最小値を見つける
  • 最小値を未整列の先頭と交換
Pythonで学ぶデータ構造とアルゴリズム

選択ソート

未整列の数値リストの模式図。1〜3番目が青、4番目がオレンジ。5番目を指すポインタが1つ。

  • 最小値を見つける
  • 最小値を未整列の先頭と交換
Pythonで学ぶデータ構造とアルゴリズム

選択ソート

未整列の数値リストの模式図。1〜3番目が青、5番目がオレンジ。5番目を指すポインタが1つ。

  • 最小値を見つける
  • 最小値を未整列の先頭と交換
Pythonで学ぶデータ構造とアルゴリズム

選択ソート

未整列の数値リストの模式図。1〜3番目が青、5番目がオレンジ。4番目と5番目を入れ替える矢印が2つ。

  • 最小値を見つける
  • 最小値を未整列の先頭と交換
Pythonで学ぶデータ構造とアルゴリズム

選択ソート

未整列の数値リストの模式図。1〜3番目が青、4番目がオレンジ。4番目と5番目が入れ替わっている。

  • 最小値を見つける
  • 最小値を未整列の先頭と交換
Pythonで学ぶデータ構造とアルゴリズム

選択ソート

未整列の数値リストの模式図。1〜4番目が青。

  • 最小値を見つける
  • 最小値を未整列の先頭と交換
Pythonで学ぶデータ構造とアルゴリズム

選択ソート

未整列の数値リストの模式図。すべて青。

  • 最小値を見つける
  • 最小値を未整列の先頭と交換
Pythonで学ぶデータ構造とアルゴリズム

選択ソート - 実装

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

選択ソート - 計算量

  • 最悪計算量: $O(n^2)$
  • 平均計算量: $\Theta(n^2)$
  • 最良計算量: $\Omega(n^2)$
Pythonで学ぶデータ構造とアルゴリズム

挿入ソート

未整列の数値リストの模式図。

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

挿入ソート

未整列の数値リストの模式図。1番目が青、2番目が他より上に持ち上げられている。

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

挿入ソート

未整列の数値リストの模式図。1番目が青、2番目が上に持ち上げられている。1番目が右にシフト。

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

挿入ソート

未整列の数値リストの模式図。2番目が青。持ち上げられた要素が1番目に配置。

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

挿入ソート

未整列の数値リストの模式図。1番目と2番目が青。

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

挿入ソート

未整列の数値リストの模式図。1番目と2番目が青。3番目が上に持ち上げられている。

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

挿入ソート

未整列の数値リストの模式図。1〜3番目が青。

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

挿入ソート

未整列の数値リストの模式図。1〜3番目が青。3番目が上に持ち上げられている。

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

挿入ソート

未整列の数値リストの模式図。1〜3番目が青。3番目が上に持ち上げられている。3番目が右にシフト。

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

挿入ソート

未整列の数値リストの模式図。1〜3番目が青。3番目が上に持ち上げられている。3番目と2番目が右にシフト。

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

挿入ソート

未整列の数値リストの模式図。1〜3番目が青。3番目が上に持ち上げられている。3番目、2番目、3番目が右にシフト。

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

挿入ソート

未整列の数値リストの模式図。1〜3番目が青。3番目が上に持ち上げられている。3番目、2番目、3番目が右にシフト。持ち上げた要素が1番目に配置。

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

挿入ソート

未整列の数値リストの模式図。1〜4番目が青。

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

挿入ソート

未整列の数値リストの模式図。1〜4番目が青。5番目が上に持ち上げられている。

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

挿入ソート

未整列の数値リストの模式図。1〜4番目が青。5番目が上に持ち上げられている。4番目が右にシフト。

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

挿入ソート

未整列の数値リストの模式図。1〜4番目が青。持ち上げた要素が4番目に配置。

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

挿入ソート - 実装

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

挿入ソート - 計算量

  • 最悪計算量: $O(n^2)$
  • 平均計算量: $\Theta(n^2)$
  • 最良計算量: $\Omega(n)$
Pythonで学ぶデータ構造とアルゴリズム

Let's practice!

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

Preparing Video For Download...