当ページのリンクには広告が含まれています。
✓目次
Insertion Sortとは
ソートアルゴリズムの一種です。
まず0番目と1番目の要素を比較し、順番が逆であれば入れ換える。次に、2番目の要素が1番目までの要素より小さい場合、正しい順に並ぶように「挿入」する（配列の場合、前の要素を後ろに一つずつずらす）。この操作で、2番目までのデータが整列済みとなる（ただし、さらにデータが挿入される可能性があるので確定ではない）。このあと、3番目以降の要素について、整列済みデータとの比較と適切な位置への挿入を繰り返す。
挿入ソート - Wikipedia
Pythonの基礎について
Insertion Sortを実装するために必要なPythonの基礎知識は、以下の記事にもまとめていますので参照ください。
ここでは、上記の記事でまとめた基礎事項に加えて学んでおくべきPythonの基礎について整理します。
[Python基礎]while文
whileはある条件が満たされる限り繰り返される処理を記述する際に使用します。
例えば以下のようなコードです。
1
2
3
4
5
6
7
8
9
| count = 0
while count < 5:
print(count)
count += 1
|
注意すべきは、上記のコードでcount += 1の記述をせずに実行すると、無限ループが発生してしまう点です。
違う書き方としては、breakを用いた書き方があります。if判定に引っかかったら、breakされる、という内容です。
1
2
3
4
5
6
7
8
9
10
11
12
| count = 0
while True:
if count >= 5:
break
print(count)
count += 1
|
また、continueを活用した方法もあります。continueは、一言でいうと、「次の文を飛ばして次のループに行ってください。」という命令になります。
breakは完全に抜けるのに対して、continueは、continueの次の行をスキップしてコードを実行させるものになります。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| count = 0
while True:
if count >= 5:
break
if count == 2:
count += 1
continue
print(count)
count += 1
|
Insertion Sortのコーディング
まずは関数を定義します。
1
2
3
| from typing import List
def insertion_sort(numbers: List[int]) -> List[int]:
|
数字の配列を簡単に設定し、定義した関数に渡してあげます。
1
2
3
4
5
6
7
8
| from typing import List
def insertion_sort(numbers: List[int]) -> List[int]:
if __name__ == '__main__':
nums = [4, 3, 2, 5, 7, 6, 1]
insertion_sort(nums)
|
設定したlistの長さを取得したいので、lenメソッドを使って取得しrangeを用いてループ文を設定します。printでindexを表示してみます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| from typing import List
def insertion_sort(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
for i in range(len_numbers):
print(i)
if __name__ == '__main__':
nums = [4, 3, 2, 5, 7, 6, 1]
insertion_sort(nums)
|
Insertion Sortアルゴリズムがどのようなものかを改めて確認します。
まず、[4, 3, 2, 5, 7, 6, 1]というリストがあった時に、まず最初に、4と3を比較します。
そのとき、前のindexの数字（今でいうと4）が、次の数字（今でいうと3）よりも大きかったら3をtempに一旦保管し、そうでなかったらそのまま、という処理をします。
そしてtmpに保管した数値と、その数値よりも前のindexに格納されている数値の大小関係の比較処理を繰り返し、tmpよりも小さかったらOK、という処理を繰り返します。
もう少しわかりやすく説明すると、ある程度処理が進んでリストとして[2, 3, 4, 5, 6, 7, 1]という状態になったとします。
同様の流れで、7と1を比較し、7の方が大きいので、1をtmpに一旦保管し、次に6とtmp(tmpは1)を比較して6のほうが大きいので次の5と比較し、5のほうが大きいので次の4と比較して・・・・という処理を繰り返し、最終的に、[1, 2, 3, 4, 5, 6, 7]という状態にするのがInsersion Sortでした。
まずは、indexが0である4と、indexが1である3を比較することを見据え、forループのrangeを1からlen_numbersの範囲にします。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| from typing import List
def insertion_sort(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
for i in range(1, len_numbers):
print(i)
if __name__ == '__main__':
nums = [4, 3, 2, 5, 7, 6, 1]
insertion_sort(nums)
|
tempは、初期値はindexが1の数値なので、temp = numbers[i]としておきます。
そして比較対象の数値は、i - 1のindexに含まれている数値なので、これをjという変数に代入しておきます。
1
2
3
4
5
6
7
8
9
10
11
12
| from typing import List
def insertion_sort(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
for i in range(1, len_numbers):
temp = numbers[i]
j = i - 1
if __name__ == '__main__':
nums = [4, 3, 2, 5, 7, 6, 1]
insertion_sort(nums)
|
ここでwhile文を用いて、jが0以上である限りループを回すようにします。こうすることで、index番号を徐々に小さくする処理を組めることになります。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| from typing import List
def insertion_sort(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
for i in range(1, len_numbers):
temp = numbers[i]
j = i - 1
while j >= 0:
print(j, end=' ')
j -= 1
print()
if __name__ == '__main__':
nums = [4, 3, 2, 5, 7, 6, 1]
print(insertion_sort(nums))
|
ここで、jを用いて、数値を入れ替えるという処理を含めます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| from typing import List
def insertion_sort(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
for i in range(1, len_numbers):
temp = numbers[i]
j = i - 1
while j >= 0:
numbers[j+1] = numbers[j]
j -= 1
print()
if __name__ == '__main__':
nums = [4, 3, 2, 5, 7, 6, 1]
print(insertion_sort(nums))
|
この入れ替え処理をいつまでやるかというと、numbers[j]がtempよりも大きい限り処理を続けさせるので、while j >= 0 and numbers[j] > temp:という風にします。
numbers[j]がtempよりも大きい限りはj + 1番目の数値と、j番目の数値を入れ替えるという処理を繰り返し、tempのほうが大きくなったら、while文を抜けます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| from typing import List
def insertion_sort(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
for i in range(1, len_numbers):
temp = numbers[i]
j = i - 1
while j >= 0 and numbers[j] > temp:
numbers[j+1] = numbers[j]
j -= 1
if __name__ == '__main__':
nums = [4, 3, 2, 5, 7, 6, 1]
print(insertion_sort(nums))
|
while文を抜けた後どうするかを考えます。
tempの数値を挿入する箇所は、j+1番目です。tempはj番目の数値と比較し、j番目の数値のほうが数が小さい場合、tempは、j + 1番目のindexに値を挿入されることが望ましいためです。
そして、numbersというリストをreturnで返却します。
コードを実行するとうまくソートされていることがわかります。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| from typing import List
def insertion_sort(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
for i in range(1, len_numbers):
temp = numbers[i]
j = i - 1
while j >= 0 and numbers[j] > temp:
numbers[j+1] = numbers[j]
j -= 1
numbers[j + 1] = temp
return numbers
if __name__ == '__main__':
nums = [4, 3, 2, 5, 7, 6, 1]
print(insertion_sort(nums))
|
固定したリストではなく、randomを活用して試してみます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| from typing import List
def insertion_sort(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
for i in range(1, len_numbers):
temp = numbers[i]
j = i - 1
while j >= 0 and numbers[j] > temp:
numbers[j+1] = numbers[j]
j -= 1
numbers[j + 1] = temp
return numbers
if __name__ == '__main__':
import random
nums = [random.randint(0, 100) for _ in range(10)]
print(insertion_sort(nums))
|
うまくいきました。
別解
以下のようなコードでも問題なくソートできました。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| from typing import List
def insertion_sort(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
for i in range(len_numbers):
count = i
while count >= 0:
if count == len_numbers - 1:
break
elif numbers[i] > numbers[i + 1]:
numbers[i], numbers[i + 1] = numbers[i + 1], numbers[i]
count -= 1
else:
count -= 1
return numbers
if __name__ == '__main__':
nums = [1, 3, 2, 5, 7, 6, 9]
print(insertion_sort(nums))
|
まとめ
本記事では、Insertion Sortを学びながら、以下のPythonの基礎を学びました。
アルゴリズムをより詳しく学びプログラミング力を高めたい方
- 以下の、Udemyのコースがおすすめです。セール時は、1200円で購入可能です。セール時でなくても、講師の方に、Twitterでクーポンコードの発行をお願い、10$(1200円)で受講可能となります。30日間の返金保証もついているので、是非試してみてください。
- 本記事も、以下のコースで学んだ内容をもとに作成しております。
現役シリコンバレーエンジニアが教えるアルゴリズム・データ構造・コーディングテスト入門
