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

○整数型の配列: 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(整数型の配列: array, 整数型: fromPos, 整数型: toPos)
  整数型: i

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

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

○整数型の配列: 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

○整数型の配列: 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

    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

○整数型の配列: 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