【擬似言語⑫追ノ弐B】挿入ソート | 入替え版（基本情報技術者, 科目B, アルゴリズム）

このNoteでは「挿入ソート（入替え版）」を学びます。
＞バブルソートのNote
＞選択ソートのNote

以下のNoteを事前学習してるとサクっと読めます。
＞【擬似言語アルゴ①】入替のNote
＞挿入ソート（シフト版）のNote

挿入ソートのシフト版と入替え版の手順は以下。

ぜひ一緒に学習を進めていきましょう！

テキストの基礎を生かして、プログラム的な考察/工夫を学んでいきます。基礎と実用にギャップを感じる方のために作りました。
＞【FEB】擬似言語の教科書Note

このNoteは、私がIT専門学校で授業したことを基に作成しています。IT専門学校でFEは第一目標として、カリキュラムが構築されています。何も知らずに入学しても、1年生10月にはFE合格していきますよ。実績ある教育ノウハウを詰め込んだので、少しでも信頼して頂けたら嬉しいです。

＞全Noteへのリンク（FE節）
※科目Aのテーマ別/科目B/旧FE午後など沢山作りました！

挿入ソートの手順と方式

＞前回のNoteでやった挿入ソートの手順。4枚のカードの場合、後ろ3枚のカードを前にどんどん並べていく感じ。軽く流して下さい。

「挿入」するので、他を右にズラす（シフト）する処理が必要でした。

下図上がシフト（水色）と挿入（紫）の様子。＞前回のNote

今回は上図下。入替え処理で「実質」的にシフトと挿入を行います。入替で右シフトを1個ずつし、挿入する値を左に1つ個ずつ進めます。改めて挿入処理する必要はないです。

関数を使ってサクっと組む

前節で手順を図示/理解できたので、更に細かい処理段階に分解します。

挿入する範囲（青）、挿入する値（緑）、挿入する場所を決め（橙）を決めて、緑から橙へ入替を繰り返していく様が分かります。

擬似言語を組みます。

シフト＋挿入が入替処理に変わっただけで、処理の流れは前回と同じ。挿入する値（緑）「i」を2から増やすループ、入替位置は「j」に格納。あとはarray[i]をarray[j]に持ってくれば良い話。＞【擬似言語⑫追ノ弐A】挿入ソート | シフト版のNote

まずは理解に集中して欲しいです。入替の連続はshiftLeftBySwap関数に丸投げしたので見やすいはず。

○整数型の配列: insertionSort_Pattern1(整数型の配列: array)
  整数型: i, j, length
  length ← arrayの要素数

  for (i を 2 から length まで 1 ずつ増やす)
    j ← i
    while ((j > 1) and (array[j - 1] > array[i]))
      j ← j - 1
    endwhile

    if (j ≠ i)
      // 連続入替関数（階層②）を呼び出す
      shiftLeftBySwap(array, i, j)
    endif
   endfor
  return array

入替を連続するshiftLeftBySwap関数は、入替を1発するswapElement関数をループで呼び出して実現しています。軽く流して下さい。＞【擬似言語アルゴ④】入替えの連続のNote

○整数型の配列: shiftLeftBySwap(整数型の配列: array, 整数型: fromPos, 整数型: toPos)
  整数型: i

  for (i を fromPos から toPos + 1 まで 1 ずつ減らす)
    // 単発の入替関数（階層③）を呼び出す
    swapElement(array, i, i - 1)
  endfor
  return array

入替を1発するswapElement関数の中身。軽く流して下さい。＞【擬似言語アルゴ①】入替のNote

○整数型の配列: swapElement(整数型の配列: array, 整数型: idx1, 整数型: idx2)
  整数型: swap
  swap ← array[idx1]
  array[idx1] ← array[idx2]
  array[idx2] ← swap
  return array

関数のブチ撒け整える

擬似言語は組めたし理解もできたので、関数をブチ撒けます。

入替を連続するshiftLeftBySwap関数の中身をブチ撒けます。変数「i」が重複してしまったので、変数「k」に改名しました。「j」も既に使ってたので、「i」,「j」の次「k」という感じ。

○整数型の配列: insertionSort_Pattern2(整数型の配列: array)
  整数型: i, j, k, length
  length ← arrayの要素数

  for (i を 2 から length まで 1 ずつ増やす)
    j ← i
    while ((j > 1) and (array[j - 1] > array[i]))
      j ← j - 1
    endwhile

    if (j ≠ i)
      // 【展開部分】連続入替関数の処理をここに直接書き込む
      for (k を i から j + 1 まで 1 ずつ減らす)
        // 単発の入替関数だけはまだ呼び出す
        swapElement(array, k, k - 1)
      endfor
    endif
  endfor
  return array

次は、swapElement関数をブチ撒けてみます。引数idx1, idx2を、k, k-1に変更して繋げます。

○整数型の配列: insertionSort_Pattern3(整数型の配列: array)
  整数型: i, j, k, swap, length
  length ← arrayの要素数

  for (i を 2 から length まで 1 ずつ増やす)
    j ← i
    while ((j > 1) and (array[j - 1] > array[i]))
      j ← j - 1
    endwhile

    if (j ≠ i)
      // 【展開部分①】連続入替のループ
      for (k を i から j + 1 まで 1 ずつ減らす)
        
        // 【展開部分②】入替関数の代入処理をここに直接書き込む
        swap ← array[k]
        array[k] ← array[k - 1]
        array[k - 1] ← swap
        
      endfor
    endif
  endfor
  return array

効率化を考える（前回と同じ）

手順（構造的）に効率が悪いです。＞前回のNote（シフト版挿入ソート） と全く同じ。

現在は3つのループがありますが。

• ❶for(iを2から～)：ソート済み範囲/挿入値を変更するループ

• ❷while(j≧2and～)：挿入位置を判定するループ

• ❸for(kをiから)：挿入値を挿入位置まで入替連続するループ

2, 3つめのループが別々なのが効率悪い。
トランプ並べて。挿入場所をずらーーーーって指して「そこか！」と決めてから、またずらーーーーーと入替えをするんですから。

以下が❷❸の擬似言語。

    while ((j > 1) and (array[j - 1] > array[i]))
      j ← j - 1
    endwhile

      for (k を i から j + 1 まで 1 ずつ減らす)
        
        // 【展開部分②】入替関数の代入処理をここに直接書き込む
        swap ← array[k]
        array[k] ← array[k - 1]
        array[k - 1] ← swap
        
      endfor

❷array[j-1]とarray[i]の比較を繰り返し、判定
❸array[k-1]とarray[k]の入替をする
一緒にやれそうですよね。

❷ループに、❸ループを組み込みました。ループカウンタ「k」を「j」に帰るだけでツジツマ合いました。

○整数型の配列: insertionSort_EfficientSwap(整数型の配列: array)
  整数型: i, j, swap, length
  length ← arrayの要素数

  for (i を 2 から length まで 1 ずつ増やす)
    j ← i
    // 挿入場所を探しながら、同時にスワップで値を押し上げていく
    while ((j > 1) and (array[j - 1] > array[j]))
      swap ← array[j]
      array[j] ← array[j - 1]
      array[j - 1] ← swap
      
      j ← j - 1 // 1つ左へ移動
    endwhile
  endfor

  return array

「k」を「j」にする際に、ループ開始/終了時の値を考えてください。ズレてるなら「-1」「+1」などの小細工が必要になります。

シフト版と入替え版の処理回数

今回の挿入ソート入替版は、シフト版よりも処理回数が多くなります。

シフト版は、挿入が最後に1回だけします。入替え版は、挿入したい値を入替処理で1歩ずつ左にズラします。

データが5個なら、処理回数の違いは2回程度でしたが。データ多くなれば入替え回数も多くなるので、差は開きます。

まとめ

お疲れ様でした！

＞前回のシフト版Note と同じ流れなので、簡単に読めたなら実力がついてる証拠です。マクロな視点は持ててます。今回は、関数を2回展開したので、変数などを整合/統一する練習になりましたね。

こんぐらいできれば、FEは合格できますよ。何度も何度も頑張ってみてください。私もまた、別アプローチや課題など考えてみたいと思います。

最後に私のお薦めの演習順番。
❶学習前の”分からせ”
＞【FEB】サンプル問題2のNote
❷テキスト
＞【FEB】擬似言語の教科書Note
＞【FEB】擬似言語の理解演習Note ←いまこの辺
↓※必要なら
うかる！ 基本情報技術者　[科目B・セキュリティ編](amazon)
うかる！ 基本情報技術者　[科目B・アルゴリズム編](amazon)
❸各年度の公開問題
＞【FEB】令和07年科目BのNote
＞【FEB】令和06年科目BのNote
＞【FEB】令和05年科目BのNote
➍解法の総復習（➋や➌と併用可）
＞【FEB】擬似言語の11の解法Note
➎模擬試験
＞【FEB】サンプル問題1のNote（擬似言語）
＞【FEB】サンプル問題1のNote（セキュリティ）