【擬似言語アルゴ②】シフトの基礎（基本情報技術者, 科目B, アルゴリズム）

このNoteでは、配列における「シフト」を学びます。「シフト」は「挿入ソート」や「基数変換」などで使います。

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

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

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

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

右/左に1つシフト

例えば、お店や健康診断。前の人が呼ばれたら、全員が1つずつ隣の席へ移る感じ。

上図の「？」はシフトで開く場所。右シフトならarray[1]、左シフトならarray[4]は、上書きがされないので、実際は元データ（[1]=5, [4]=8）が残ってます。

でもシフトをしたので、元データを残すわけにはいきません。

とりあえず今回は「0」を入れるとします（上図の「？」を「0」にするって意味）。

２つの注意点 | 順番と空きの値

「右シフト」は、要素番号の大きい方にズラす処理。

2つの注意点を認識しましょう。

上図の右。要素番号の小さい順にシフト処理をすると、次にシフトすべきデータを上書きしてしまって、大変な状態になってますね。

どうせ「破棄」するんだから、移動する手間などかけず、上書きさせちゃえば良いんです。

そもそも「（配列の外に）移動して破棄」が出来ません。

上図ならarray[4]=8を配列の外に移動させてますが。できません。array[]={5, 6, 7, 8}なので、[1]～[4]までしか使えないです。array[5]が使えません。

右シフトの擬似言語

前々節・前節で3つの方針が立ちました。
【A】空きには「0」を入れる
【B】右（要素番号が大きい順）から右シフト処理する
【C】シフト処理するのは、[1]～[要素数－1]。

処理手順の図解（左）から規則性（右）を見出して、ループカウンタや具体的な擬似言語を考えていきます。

○整数型の配列: rightShift(整数型の配列: array)
  整数型: i, length
  
  length ← arrayの要素数
  
  / 1. 後ろの要素から順番に、1つ右（i+1）の場所へコピーする */
  for (i を length-1 から 1 まで 1 ずつ減らす) / 【B, C】 */
    array[i + 1] ← array[i]
  endfor
  
  / 2. 空いた先頭のマスに新しい値を入れる */
  array[1] ← 0 / 【A】 */

  return array

左シフトの擬似言語

配列の前（要素番号が小さい方）にズレる処理が「左シフト」。

左シフトの方針も右シフトと同様に考えて。
【B, C】が若干変わります。
【A】空きには「0」を入れる
【B】左（要素番号が小さい順）から左シフト処理する
【C】シフト処理するのは、[2]～[要素数]。

前節と同様に、シフト処理【B】をループ処理【C】させた後、0埋め処理【Ａ】をします。

手順→処理のブロックも決まったので、擬似言語に変換。

○整数型の配列: leftShift(整数型の配列: array)
  整数型: i, length
  
  length ← arrayの要素数
  
  / 前から順番に、1つ左（i）の場所へ右隣（i+1）の要素をコピーする */
  for (i を 2 から length まで 1 ずつ増やす) / 【C】 */
    array[i-1] ← array[i]                  / 【B】 */
  endfor
  
  / 空いた末尾のマスに新しい値（例えば0）を入れる */
  array[length] ← 0 / 【A】 */

  return array

空きに何を入れるか

色んな考えがあります。

今回はとりあえず「0」を入れました。

テストの点数など、0未満が”あり得ない”なら「-1」も良き。

科目Bだと「未定義の値」を代入することも。
＞【FEB】サンプル1問11のNote

さらに、ハミ出したデータを入れ直すことも。
上図の右シフトでハミだしたarray[4]=8をarray[1]に入れる。
上図の左シフトでハミだしたarray[1]=5をarray[4]に入れる。
※「循環シフト」「環状シフト」「ビット回転」などと云われます（ wikipedia）

例えば、{5, 6, 7, 8}を、
右シフトしたら{8, 5, 6, 7}
左シフトしたら{6, 7, 8, 5}
となる感じ。

さらにさらに、「論理シフト」「算術シフト」ってシフトもあります（次節）。

おまけ | 論理/算術シフト

例えば、私たちが使ってる10進数。10を”左”シフトしたら100、”×”10ですね。”右”シフトしたら1、”÷”10ですね。

2進数でも同じ。2進数10（=2）を”左”シフトしたら100（=4）、”×”2。”右”シフトしたら1（=1）、”÷”2ですね。

コンピュータの中では2進数のシフトで掛け算/割り算してます。

FE科目A対策にもなるので、「論理シフト」「算術シフト」まで少し補強。

シフト演算には2種類あります。

• 論理シフト（0を追加する）

  • 左シフト：010→100

  • 右シフト：010→001, 110→011

• 算術シフト

  • 左シフト：011→010, 101→110（最上位ビットは変わらない）

  • 右シフト：010→001, 110→111（追加するビットが違う）

  • 左の算術シフトでは、最上位ビットはそのまま。右の算術シフトは、最上位ビットをコピペするので、ややこしい。

算術シフトが複雑なのは「正負の符号（＋－）」を数に含めているからです。

なぜ、左端をコピーするのかは、難しい「補数」の理解が必要。私のNoteでも少し触れましたが、メイン目的ではないので割愛します。詳しくはWeb検索やテキストで勉強して下さい。すみません。【FE計算⓳】シフト演算のNote

まとめ

お疲れ様でした！

今回は、1個分のシフトで基礎を固めました。「シフト」は、シフトする順番、破棄されるデータ、空になる配列要素への考慮が必要ってのが分かったでしょうか？

次回「シフト」を深めます。

実用では、2個や3個分のシフト、配列の一部分をシフトする処理も使います。関数にして「挿入ソート」の擬似言語で呼び出すだけにし、見通しを良くするために。＞【擬似言語アルゴ③】複雑なシフトのNote（作成中＊）

課題。rightShift関数とleftShift関数を統合して、引数が正値なら右シフト、負値なら左シフト、0ならそのままの配列を返す関数にして下さい。if文で3パターン作るだけなので、簡単です。

課題。左シフト「array[i-1] ← array[i]」を「array[i] ← array[i+1]」で組んでください。for文の条件式を再考してください。

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