挿入ソートの仕組みを徹底解説！アニメーションで学ぶ「正しい位置に差し込む」ソート・単純挿入法【ソートアルゴリズム入門】#2

単純ソート３種のうちの一つ”単純挿入ソート”

ソートアルゴリズムのうち、単純な並び替えでソート(並び替え)を行うものとして、挿入ソート・バブルソート・選択ソートがあり、これらを単純ソートと呼びます。

挿入ソートの実行例　アニメーション

（※このほかにも、比較的低性能なソートを単純ソートと呼ぶ場合がある)

今回は、その中でも直感的で分かりやすい単純ソート、「挿入ソート（Insertion Sort）」の仕組みと動きを解説します。

「挿入ソート」は、トランプの手札を配られた順に並べ替えるとき、私たちが無意識に行っている動作にそっくりです。この記事では、実際にステップごとにどのような処理をするのかアニメーション付きで整列を行うツールを使いながら、挿入ソートについて理解していきましょう。

11 記事

シリーズ

ソートアルゴリズム

ソートアルゴリズムについて、単純ソート、分割統治法などの比較するソート、基数ソートなどの比較しないソートまでその仕組みを...

1. 挿入ソート（Insertion Sort・単純挿入法）とは？

挿入ソートは、「すでに整列されている部分」に、「新しい要素」を「正しい位置」に「挿入（Insert）」していくアルゴリズムです。

トランプの手札で例えると…

1. あなたはカードを1枚ずつ引いて、手札に加えていきます。
2. 2枚目のカードを引いたら、1枚目のカードと比べて、正しい順序（例：昇順）になるように持ち替えます。（この時点で、手札の2枚は整列済み）
3. 3枚目のカードを引いたら、すでに整列済みの手札（2枚）を見て、そのカードが「入るべき場所」を見つけて、そこに差し込みます。
4. 4枚目、5枚目…と、新しいカードを引くたびに、「整列済みの手札」の「適切な場所」に「挿入」していきます

この「整列済み」と「未整列」に分け、未整列の先頭を整列済みの適切な場所に挿入していく動作が、挿入ソートの基本的な考え方です。

2. 挿入ソートでトランプを並び替えたら？

一枚目を並べる

二枚目を比較して並べる

三枚目を比較して並べる

四枚目を比較して並べる。すでに並べてあるカード(5)と比べて大きく、Ｊよりは小さいのでその間に挿入する。

五枚目を比較して並べる。すでに並べてあるカード(5)と比べて大きく、10よりは小さいのでその間に挿入する。

以下繰り返して全部並べるまで続けたら、並び替え完了。

3. 挿入ソートの動きを見てみよう！

挿入ソートで並び替えを試せます。ステップ実行ボタンを押して、並び替えを進めてみてください。

緑色が今挿入したいデータで、黄色が今比較している対象です。

挿入ソートの疑似コード(ソートの手順)

手元で試せる環境があったら自身の慣れているプログラミング言語で以下の処理を書いてみると理解が深まると思います。

algorithm InsertionSort(L) is
  n ← length of L
  
  // i: 未ソート部分の先頭インデックス。
  // (1 から n-1 まで、1ずつ増やす)
  for i from 1 to n-1 do
    
    // j: ソート済み部分のインデックス。
    // (i-1 から 0 まで、1ずつ減らす)
    j ← i - 1
    
    // j が 0 以上 かつ L[j] > L[j+1] (左 > 右 で逆順) の間、
    // 交換しながら左へ進む
    while j >= 0 and L[j] > L[j+1] do
      
      // L[j] と L[j+1] を交換
      temp ← L[j]
      L[j] ← L[j+1]
      L[j+1] ← temp
      
      j ← j - 1 // 1つ左へ
    end
    // (逆順でなくなれば while が終了し、次の i へ)
    
  end
  
  return L
end

まとめ

• 挿入ソートは、「整列済みの場所に、新しい要素を差し込む」アルゴリズム。
• トランプの手札を並べ替えるイメージ。
• データが少ない場合や、ほとんど整列済みの場合は高速だが、データ数が多くなると遅い。

次は、単純ソートの3つ目「バブルソート」の仕組みを見ていきましょう！

バブルソートの仕組みを徹底解説！アニメーションで学ぶ「ひたすら比較・交換」ソート・単純交換【ソートアルゴリズム入門】#3

ソート入門の定番「バブルソート」の仕組みを解説。隣同士を比較して交換するだけの単純な動きを、インタラクティブなツールで1ステップずつ追体験できます。重い（大きい）値が水底に沈んでいく（＝末尾に確定する）様子をアニメーションで学びましょう。

11 記事

シリーズ

ソートアルゴリズム

ソートアルゴリズムについて、単純ソート、分割統治法などの比較するソート、基数ソートなどの比較しないソートまでその仕組みを...

単純ソートの計算量は？(単純ソートを全て閲覧して理解した後推奨(11/13公開予定))

計算量 とは？データ数が倍になると手間が4倍？単純ソートの計算量O[n^2]を中学生でもわかるように解説【ソートアルゴリズム入門】#4

なぜ単純ソートはデータが増えると遅くなる？その「遅さ」を測るモノサシが「計算量」と「O記法」です。この記事では、O(n^2) といった計算量の考え方を、中学生でもわかる「作業の手間」に例えて解説。グラフで「増え方の勢い」を学び、次の高速なアルゴリズムへ進みましょう。