プログラム

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

2019年4月7日

はじめに

基本情報技術者試験や応用情報技術者試験でよく出題される整列アルゴリズムの問題。

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

スポンサーリンク

本記事では、"整列済み"と"未整列"の2つに分け"未整列"から1つずつ"整列済み"へ挿入していく挿入ソート（基本挿入法）について図解で分かりやすく解説していきます。

挿入ソート（基本挿入法）とは

挿入ソート（基本挿入法）とは"未整列の配列"から1つずつ値を取り出し"整列済み配列"の適切な位置へ挿入していく手法です。

挿入ソートな流れ

  • "未整列配列"から値から1つ取り出す
  • 取り出した値を"整列済み配列"の適切な位置に挿入する
  • 処理1と2を繰り返し"未整列配列"の全データを"整列済み配列"に挿入したら完了

暗記ポイント

挿入ソートは"未整列な配列"から1つずつ値を取り出し"整列済み配列"の適切な位置に挿入する整列アルゴリズム

それでは、図を利用して挿入ソートの流れを解説していきます。

【手順1】未整列の配列から先頭の値を取り出し、整列済みの配列に挿入

"未整列の配列"から先頭の値「4」を取り出し"整列済みの配列"に挿入します。（"整列済みの配列"は空なので、先頭に「4」を挿入する）

挿入ソート手順1

【手順2】未整列の配列から2番目の値を取り出し、整列済みの配列に挿入

"未整列の配列"から2番目の値「3」を取り出し、次の条件に一致した"整列済みの配列"の位置に挿入します。

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

挿入ソート手順2

【手順3】未整列の配列から3番目の値を取り出し、整列済みの配列に挿入

"未整列の配列"から3番目の値「5」を取り出し、次の条件に一致した"整列済みの配列"の位置に挿入します。

  1. "整列済みの配列"の末尾の値「4」と比較
  2. 「5」は「4」より大きいので最後尾に挿入

挿入ソート手順3

【手順4】未整列の配列から4番目の値を取り出し、整列済みの配列に挿入

"未整列の配列"から4番目の値「7」を取り出し、次の条件に一致した"整列済みの配列"の位置に挿入します。

  1. "整列済みの配列"の末尾の値「5」と比較
  2. 「7」は「5」より大きいので最後尾に挿入

挿入ソート手順4

スポンサーリンク

【手順5】未整列の配列から5番目の値を取り出し、整列済みの配列に挿入

"未整列の配列"から5番目の値「1」を取り出し、次の条件に一致した"整列済みの配列"の位置に挿入します。

  1. "整列済みの配列"の末尾の値から順番に比較
  2. 「1」は「3」より小さいので先頭に挿入

挿入ソート手順5

【手順6】未整列の配列から6番目の値を取り出し、整列済みの配列に挿入

"未整列の配列"から6番目の値「8」を取り出し、次の条件に一致した"整列済みの配列"の位置に挿入します。

  1. "整列済みの配列"の末尾の値「7」と比較
  2. 「8」は「7」より大きいので最後尾に挿入

挿入ソート手順6

【手順7】未整列の配列から7番目の値を取り出し、整列済みの配列に挿入

"未整列の配列"から7番目の値「6」を取り出し、次の条件に一致した"整列済みの配列"の位置に挿入します。

  1. "整列済みの配列"の末尾の値から比較
  2. 「6」は「7」より小さくて「5」より大きいので、「5」と「7」の間に挿入

挿入ソート手順7

【手順8】未整列の配列から8番目の値を取り出し、整列済みの配列に挿入

"未整列の配列"から8番目の値「2」を取り出し、次の条件に一致した"整列済みの配列"の位置に挿入します。

  1. "整列済みの配列"の末尾から比較
  2. 「2」は「3」より小さくて「1」より大きいので、「1」と「3」の間に挿入

挿入ソート手順8

未整列の要素を全て整列済みに挿入できたので「挿入ソート」による整列は終了です。

 

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

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

helpful