【擬似言語アルゴ④】入替えの連続（基本情報技術者, 科目B, アルゴリズム）

このNoteでは、”入替えの連続でシフト処理”してみます。

例えるなら。並んで席に座ってる時。「隣の人と席を替わる」を次々に繰り返していくと、自分はどんどん前へ進み、他の人たちは全員1つずつ後ろにずれていくのを想像すると、ちょっとは見当がつくかな。

「挿入ソート」は、”擬似言語のラスボス❷”。挫折しちゃう所なので、段階的に学習できるように作ってみました。
＞【擬似言語アルゴ①】入替のNote
＞【擬似言語アルゴ②】シフトのNote
＞【擬似言語アルゴ③】一部をシフトのNote
＞【擬似言語アルゴ④】入替えシフトのNote　←いまここ
＞【擬似言語⑫追2】挿入ソートのNote（作成中＊）

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

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

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

入替えの連続 で シフト/挿入する

下図左が、シフトして挿入する手順です。＞前回のNote

今回は下図右。入替を連続しても同じ結果になります。

左図：シフトすると元データ上書きされるから退避が必要。右図：入替なら上書きを防ぎつつシフト（すれ違い）してます。

ここで、配列の要素番号（添え字）とループカウンタの目途が付きます。
[i-1]と[i]を入れ替えるとして。
i=from～to+1 まで減らす。

図の場合。
[i-1]と[i]の入替を、i=4～3でループさせるので、
[3]と[4]の入替。[2]と[3]の入替。

関数を繰り返し呼び出す

擬似言語を組みます。

＞【アルゴ①】入替のNote で、入替処理する「swapElement関数」を作ったので、ループ処理で繰り返し呼び出してみます。

前節の図右で立てた方針は2点。
・[i-1]と[i]を入替える
・i=from～to+1まで
 ※from > toなので、「1ずつ減らす」制御

swapElement関数を繰り返し呼び出します。

○整数型の配列: rightShiftRangeBySwap(整数型の配列: array, 整数型: fromPos, 整数型: toPos)
  整数型: k

  for (k を fromPos から toPos + 1 まで 1 ずつ減らす)
    array ← swapElement(array, k, k - 1)
  endfor
  return array

※「from」「to」だと擬似言語では分かりにくいので、「fromPos」と「toPos」としました。

「fromPos」と「fromPos-1」を入れ替えて、
「fromPos-1」と「fromPos-2」を入れ替えて…、
と続いて、
「toPos+1」と「toPos」を入れ替えて終了。

前節のfrom=[4], to=[2]の時。
[4]と[3]を入れ替えて、
[3]と[2]を入れ替えて終了、
となります。

関数をブチ撒けてみる

rightShiftRangeBySwap関数内で、swapElement関数の中身をぶち撒けてみます。

  for (k を fromPos から toPos + 1 まで 1 ずつ減らす)
    array ← swapElement(array, k, k - 1)
  endfor

に、

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

って中身をブチ撒きます。

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

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

  return array

関数をブチ撒けて、変数名の統一（idx=i, idx=i-1）。

なお、変数名が被っていたら、そのままか/別名にする場合もあり。今回はなし。arrayはそのままでOK。swapもそのままでOK。

例えば、swapElementで「変数i」使ってて、rightShiftRangeBySwapでも「変数i」を使ってたら、ゴッツンコするので、片方を「変数j」とかに変更します。ループカウンタは「i」「j」で組むから被り易いかも。

テキストや科目Bは「こんぐらい組んでね」と、いきなり来ます。ちょっとハードルあるので理解できない学生さんもいました。

私のNoteでは、関数化してからブチマケル方向で作ってみました。実際の開発でも、関数やクラスは細かく分けますし。統合もあるでしょう。

処理手順と処理回数

左図シフト方式は少し離れ業に見えますが、処理回数は少なくてスマート。右図入替え方式は処理回数が多くなります。変数は、左はtmp, 右はswapを使うので、メモリ使用量は引き分け。

データが5個なら、処理回数が4回だの6回だので軽微です。でも、データが多くなるほど、回数差は大きくなります。

まとめ

お疲れ様でした！

これで挿入ソートの準備が出来ました。

挿入ソートは2回学びます。

＞【擬似言語アルゴ③】一部をシフト
＞【擬似言語⑫追ノ弐】挿入ソート | シフト版のNote（準備中＊）

今回のNoteは
＞【擬似言語⑫追ノ弐】挿入ソート | 入替版のNote（準備中＊）
で使います。

どちらも、挿入ソートの手順を図解で理解し、シフト/入替えの関数を使って、なるべく簡単に擬似言語を組みます。そして関数をブチ撒けて、整えます。

こんな感じで、基礎を生かして実例で擬似言語を作って、さらにプログラム的な考察や工夫を深めていきたくて、理解シリーズを作ってます。＞【FEB】擬似言語の教科書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（セキュリティ）