挿入ソート(基本挿入法)とは

プログラム

挿入ソート(基本挿入法)とは | 分かりやすく図解で解説

はじめに

情報処理試験問題でよく登場する整列アルゴリズムの問題。

基本的な整列アルゴリズムには「バブルソート」「選択ソート」「挿入ソート」があります。そしてより高速な整列アルゴリズムには「シェルソート」「クイックソート」「ヒープソート」「マージソート」などがあります。

スポンサーリンク

本記事では、「整列済み」と「未整列」の2つに分け「未整列」から1つずつ「整列済み」へ挿入していく「挿入ソート(基本挿入法)」について図解を利用してわかりやすく解説しています。

挿入ソート(基本挿入法)とは

挿入ソートとは、「未整列な配列」から値を1つずつ取り出し「整列済み配列」の適切な位置に挿入していく手法です。

  1. 「未整列配列」から値から1つ取り出します。
  2. 取り出した値を「整列済み配列」の適切な位置に挿入します。
  3. 1と2を繰り返し全て「整列済み配列」に挿入し終われば完了となります。

 

それでは具体的に図解で挿入ソートの流れを説明していきます。

 

暗記ポイント:挿入ソートは「未整列な配列」から1つずつ取り出し「整列済み配列」の適切な位置に挿入する整列アルゴリズム

【手順1】未整列の配列から"4"を取り出し、整列済みの配列に挿入する

「未整列の配列」から"4"を取り出し、「整列済みの配列」に挿入します。

「整列済みの配列」は空なので、先頭に"4"を挿入します。

挿入ソート手順1

【手順2】未整列の配列から"3"を取り出し、整列済みの配列に挿入する

「未整列の配列」から"3"を取り出し、「整列済みの配列」に挿入します。

  1. 「整列済みの配列」の"4"と比較します。
  2. "3"は"4"より小さいので"4"の左側に"3"を挿入します。

挿入ソート手順2

【手順3】未整列の配列から"5"を取り出し、整列済みの配列に挿入する

「未整列の配列」から"5"を取り出し、「整列済みの配列」に挿入します。

  1. 「整列済みの配列」の"3"と比較します。"5"は"3"より大きいので次へ
  2. 「整列済みの配列」の"4"と比較します。"5"は"4"より大きいので次へ
  3. "5"は「整列済み配列」の中で一番大きいので、最後尾に追加します。

挿入ソート手順3

【手順4】未整列の配列から"7"を取り出し、整列済みの配列に挿入する

「未整列の配列」から"7"を取り出し、「整列済みの配列」に挿入します。

  1. 「整列済みの配列」の"3"と比較します。"7"は"3"より大きいので次へ
  2. 「整列済みの配列」の"4"と比較します。"7"は"4"より大きいので次へ
  3. 「整列済みの配列」の"5"と比較します。"7"は"5"より大きいので次へ
  4. "7"は「整列済み配列」の中で一番大きいので、最後尾に追加します。

挿入ソート手順4

スポンサーリンク

【手順5】未整列の配列から"1"を取り出し、整列済みの配列に挿入する

「未整列の配列」から"1"を取り出し、「整列済みの配列」に挿入します。

  1. 「整列済みの配列」の"3"と比較します。
  2. "1"は"3"より小さいので"3"の左側に"1"を挿入します。

挿入ソート手順5

【手順6】未整列の配列から"8"を取り出し、整列済みの配列に挿入する

「未整列の配列」から"8"を取り出し、「整列済みの配列」に挿入します。

  1. 「整列済みの配列」の"1"と比較します。"8"は"1"より大きいので次へ
  2. 「整列済みの配列」の"3"と比較します。"8"は"3"より大きいので次へ
  3. 「整列済みの配列」の"4"と比較します。"8"は"4"より大きいので次へ
  4. 「整列済みの配列」の"5"と比較します。"8"は"5"より大きいので次へ
  5. 「整列済みの配列」の"7"と比較します。"8"は"7"より大きいので次へ
  6. "8"は「整列済み配列」の中で一番大きいので、最後尾に追加します。

挿入ソート手順6

【手順7】未整列の配列から"6"を取り出し、整列済みの配列に挿入する

「未整列の配列」から"6"を取り出し、「整列済みの配列」に挿入します。

  1. 「整列済みの配列」の"1"と比較します。"6"は"1"より大きいので次へ
  2. 「整列済みの配列」の"3"と比較します。"6"は"3"より大きいので次へ
  3. 「整列済みの配列」の"4"と比較します。"6"は"4"より大きいので次へ
  4. 「整列済みの配列」の"5"と比較します。"6"は"5"より大きいので次へ
  5. 「整列済みの配列」の"7"と比較します。"6"は"7"より小さいので"7"の左側に"6"を挿入します。

挿入ソート手順7

【手順8】未整列の配列から"2"を取り出し、整列済みの配列に挿入する

「未整列の配列」から"2"を取り出し、「整列済みの配列」に挿入します。

  1. 「整列済みの配列」の"1"と比較します。"2"は"1"より大きいので次へ
  2. 「整列済みの配列」の"3"と比較します。"2"は"3"より小さいので"3"の左側に"2"を挿入します。

挿入ソート手順8

 

未整列の要素を全て整列済みに挿入できたので、これで挿入ソートは終了です。

 

[基本整列アルゴリズム]

[高速整列アルゴリズム]

\ 参考になりましたか? /

© 2020 ITを分かりやすく解説