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

このNoteでは「挿入ソート（シフト版）」を学びます。
ソート3種類目。
＞バブルソートのNote
＞選択ソートのNote

ネオ・ラスボス・サイクロンジェット・ラスボスです。
これでもかなり下準備をしたんですが。
＞【擬似言語アルゴ①】入替のNote
＞【擬似言語アルゴ②】シフトのNote
＞【擬似言語アルゴ③】一部をシフトのNote

かなりマッシブになりました。（目次見てください）。

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

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

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

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

挿入ソートの手順

手順を図解にして理解します。

4枚のカード。前にどんどん並べていきます。

1枚目の「3」はそのまま。2枚目「4」は「3」より大きいので右。3枚目「1」は一番左へ。って、直接挿入していきます。

もう少し詳しく書くと。
・挿入位置を決める
・挿入する場所より右側を右にずらす（シフト）
・挿入位置に挿入する
って3つの処理が必要です。

シフト版 | 統一した処理を見出す

※「シフト版」と書いたのは「入替版」も学びたいからなので気にせず。＞【擬似言語⑫追ノ弐②】挿入ソート | 入替え版のNote＊

擬似言語を組むので更に細かく手順を明らかにします。ちょっとデータも替えて色んなケースを出しておきました。

色んな処理がするようなデータにしました。シフト不要・左端に挿入・中間に挿入と、させましたが、❶～❹の統一処理が見いだせれば勝ち。

下図コメントの【１】～【４】が❶～❹に対応します。

○整数型の配列: insertionSort(整数型の配列: array)
  整数型: i, j, length, tmp
  
  length ← arrayの要素数
  
  / 2番目の要素から順番に、挿入する位置を探していく 【1】*/
  for (i を 2 から length まで 1 ずつ増やす)
    
    / 現在チェックしている（挿入したい）値を退避させておく 【2】*/
    tmp ← array[i]
    
    // 挿入すべき正しい位置（j）を探す
    j ← i
    while (j > 1 かつ array[j - 1] > tmp)
      j ← j - 1
    endwhile
    
    / もし挿入位置（j）が自分自身（i）と違うなら、
      間を右にずらして割り込ませる 【３】*/
    if (i ≠ j)
      array ← rightShiftRange(array, j, i)
      array[j] ← tmp / 空いた場所に値を入れ直す 【４】*/
    endif
    
  endfor

  return array

右シフトには、rightShiftRange関数を使いました。すっきり見えますから。＞【擬似言語アルゴ③】一部をシフトのNote

【1】～【4】のブロック。ループカウンタ「i」が挿入させる値の位置。「j」が挿入させるべき位置。tmpが挿入させる値を一旦補完する変数。

次節でループカウンタの設計経緯を解説しますが。そんなのはともかくトレースしちゃえば動きは分かります。トレース最強ですから。

くっそ面倒だけど、何度か挑戦です。途中まででも構いません。一度やらんことには「そういうことね」って経験/実感/センスが身につきません。

ループカウンタの役割/始値/終値

forやwhileのループカウンタ（i, j）の役割を理解し、始値/終値が正しいか確認していきます。

まず「i」から。

  / 2番目の要素から順番に、挿入する位置を探していく 【1】*/
  for (i を 2 から length まで 1 ずつ増やす)

挿入する値は、2枚目のカードからだったので、i=2から始まってます。

挿入する値は、配列の要素数まで。4個なので[4]まで考えます。よって、 iの終値は4まで。

予め「length ← arrayの要素数」で値を取ったので「i=2～length」でループを組みました。

次は「j」を考えます。

    // 挿入すべき正しい位置（j）を探す
    j ← i
    while (j > 1 かつ array[j - 1] > tmp)
      j ← j - 1
    endwhile
    

「j」は「i」で指定した値をどこに挿入するかを指します。

挿入候補は下図だと。
[1]
[1][2]
[1][2][3]
と変化してます。

挿入する場所を決めるには、挿入する値array[i]と挿入候補を比べます。例えば上図左下なら、tmpとarray[2]を比べて、array[1]と比べて、array[1]に挿入すべきだ、と反転してます。

tmp=array[3]=array[i]をarray[2]・array[1]と比べていくループを、「j」で制御すると考えると。
・jをiから始めるなら【Ａ】
・array[j-1]と比較するのを【Ｂ】
・jを1ずつ減らしてループ【Ｃ】
と発想します。

ループ終了はarray[1]なので
array[j-1]だから
j-1>0なので j>1までとなります。【Ｄ】

擬似言語を見てみます。

    / 挿入すべき正しい位置（j）を探す */
    j ← i       / 【A】*/
    while (j > 1 かつ array[j - 1] > tmp) / 【B】【D】*/
      j ← j - 1 /【C】*/
    endwhile

「j-1」にしたのと、「j>1つまりj≧2」にしたのが気持ち悪いかもですが、シフト範囲の指定が楽なので敢えてです（下図）。

右シフトする範囲は、挿入すべき場所（j）から挿入する値の場所（i）までです。

jループで「j-1」としたことで、rightShiftRange(j, i)って分かり易い引数にできました。これがrightShiftRange(j+1, i-1)とか妙な小細工入ると後で分かりにくくなりますね。

どこかで「-1」「+1」の小細工は必要になりますが。どこに仕込むかは、設計思想/ルール/好みにはなります。

関数をブチ撒ける | 変数を整合させる

rightShiftRange関数をブチ撒けます。

とはいえ、挫折する学生さんも多いので、前段で入替やシフトのアルゴリズムと擬似言語組みを段階的に準備してきたんです。
＞【擬似言語アルゴ①】データの入替のNote
＞【擬似言語アルゴ②】シフトの基礎のNote
＞【擬似言語アルゴ③】一部をシフトのNote

rightShiftRange関数を展開しました。

ただし、ループカウンタ「i」が使われてるので注意。

  for (i を endPos - 1 から startPos まで 1 ずつ減らす)
    array[i + 1] ← array[i]
  endfor

変数「i」は、insertionSort関数でも使われているので、ループが狂ってしまいます。rightShiftRange関数側を「i」から「k」に変名しました。

○整数型の配列: insertionSort(整数型の配列: array)
  整数型: i, j, k, length, tmp  // 内側用に変数 k を追加
  
  length ← arrayの要素数
  
  / 2番目の要素から順番に、挿入する位置を探していく */
  for (i を 2 から length まで 1 ずつ増やす)
    
    // 現在チェックしている（挿入したい）値を退避させておく
    tmp ← array[i]
    
    // 挿入すべき正しい位置（j）を探す
    j ← i
    while (j > 1 かつ array[j - 1] > tmp)
      j ← j - 1
    endwhile
    
    // もし挿入位置（j）が自分自身（i）と違うなら、間を右にずらして割り込ませる
    if (i ≠ j)
      // 【rightShiftRange の中身を展開・変数を k に変更】
      // 終点（i）の手前から順番に、始点（j）まで右へコピーする
      for (k を i - 1 から j まで 1 ずつ減らす)
        array[k + 1] ← array[k]
      endfor
      
      // 空いた始点（j）のマスを 0 にする
      array[j] ← 0
      
      array[j] ← tmp / 値を挿入 */
    endif
    
  endfor

  return array

２つの無駄な処理

さて、無駄処理が混じってるのが分かるでしょうか。

1つめは簡単。

      array[j] ← 0
      
      array[j] ← tmp / 値を挿入 */

「array[j] ← 0」の0埋めが無駄ですね。どうせtmpを代入するんだから。

2つめは構造です。

1. 挿入する範囲を決める（iループ）

2. 挿入する値を退避させる（tmp）

3. 挿入する場所を探す（jループ）

4. 挿入する場所より右を右シフト（kループ）

5. 右シフトで開いた左シフトに0代入（1点目で指摘済み）

6. 挿入する場所に値（2）を代入

3と4のループを別々にしてるのが無駄（非効率）。挿入すべき位置を探しつつシフトしつつ挿入すれば良いと。

だって、トランプ並べてて。挿入場所をずらーーーーって指して「そこか！」と決めてから、またずらーーーーーと右シフトしていって挿入するんですから。

    j ← i
    while (j > 1 かつ array[j - 1] > tmp)
      j ← j - 1
    endwhile

      for (k を i - 1 から j まで 1 ずつ減らす)
        array[k + 1] ← array[k]
      endfor

挿入場所をずらーーーーっと探しながら、右シフトもしちゃえばループ1回で済むはずですよね（次節）。

効率版 | 挿入探索とシフトを同時に

挿入位置探しのループ（j）に、シフト処理を組み入れました。

    // 2. 左隣が退避した値（tmp）より大きい間、要素を右に1マスずつずらす
    while ((j > 1) and (array[j - 1] > tmp))
      array[j] ← array[j - 1]
      j ← j - 1
    endwhile

シフト式の要素番号を小細工します。

• 前：array[k + 1] ← array[k]

• 後：array[j] ← array[j - 1]

前回「jはiからループ」「kはi-1からループ」で「1」ズレてるので。kをjに置き換えて「-1」して、ズレを修正。

擬似言語の全容。

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

  for (i を 2 から length まで 1 ずつ増やす)
    // 1. 挿入したい現在の値を一時的に退避させる
    tmp ← array[i]
    j ← i

    // 2. 左隣が退避した値（tmp）より大きい間、要素を右に1マスずつずらす
    while ((j > 1) and (array[j - 1] > tmp))
      array[j] ← array[j - 1]
      j ← j - 1
    endwhile

    // 3. 空いた正しい位置に、退避させておいた値をカチッとはめ込む
    array[j] ← tmp
  endfor

  return array

まとめ

お疲れ様でした！

シフト関数を準備したので、テキストよりはサクっと組むとこまでは行けましたが。関数ブチ撒け、からの、ループの役割や課題などで大混乱だったかもですね。

もう一度流れの確認。

挿入ソートの手順を学び、擬似言語を組みました。右シフト関数を使ってサクっと組みました。
挿入ソートにおけるループカウンタの役割を解釈して、始値と終値が正しいか確認しました。関数をブチ撒けて、コードを整えました。さらにさらに処理の効率化をしました。

何度も何度も頑張ってみてください。私もまた、別アプローチや課題など考えてみたいと思います。

とりま課題を2つ出しました（トレース、前から比較への改造）。答えのNoteはまた機会ある時に作る…と思います（未定💦）。

最後に私のお薦めの演習順番。
❶学習前の”分からせ”
＞【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（セキュリティ）