情報処理技術者試験対策 > アルゴリズム > インサーションソート

インサーションソートについての説明

インサーションソート(挿入ソート)は、数値を適切な場所に挿入していくことにより並べ替えを行うアルゴリズムをいいます。具体的には、下記のような手順で並べ替えを行います。

  1. まず、左から2つの数字を比較して小さい数字が左、大きい数字が右に来るようにする。
  2. 次に、左から3つ目の数字を、その並べ替えられた2個の数字と比較して、適切な位置に挿入する
  3. その次に、左から4つ目の数字を、その並べ替えられた3つの数字と比較して、適切な位置に挿入する。
  4. 上記1から3を繰り返す

今回も、下のような適当に並んでいる数字を、右のように並べ替える、というのを例にして考えていきたいと思います。

3 5 4 2 8 1 6 9 7 → 1 2 3 4 5 6 7 8 9

インサーションソートのアルゴリズム具体例

1巡目

インサーションソート1巡目

左の2つの数字を比較して小さい数字が左、大きい数字が右に来るように並べ替えます。

※この段階で左の2つの数字は、すでに順序が確定しており、この2つの位置が入れ替わることはない、ということが重要です。


2巡目

インサーションソート2巡目

左から3つ目の数字(=4)を、その並べ替えられた2つの数字と比較して、適切な位置に挿入する



3巡目

インサーションソート3巡目

左から4つ目の数字(=2)を、その並べ替えられた3つの数字と比較して、適切な位置に挿入する。


4巡目

インサーションソート4巡目

左から5つ目の数字(=8)を、その並べ替えられた4つの数字と比較して、適切な位置に挿入する。


というように、全ての数の並べ替えが終わるまで続けていきます。

カテゴリ一覧
アルゴリズム
アルゴリズムとは  ソートアルゴリズム  バブルソート  インサーションソート  クイックソート  マージソート  ソートアルゴリズムを体感する