入替えとシフト

2つの要素を入れ替える

配列の要素を入れ替える操作は、整列の章でずっと使います。ここで形を身につけておきます。

まず、素直に書いて失敗する例を見ます。

data[1] ← data[2] data[2] ← data[1]

これでは入れ替わりません。1行目で data[1] が上書きされているので、2行目の右辺はすでに新しい値です。結果は、両方が data[2] の値になってしまいます。

正しくは、退避用の変数を1つ用意します。

整数型: taihi taihi ← data[1] data[1] ← data[2] data[2] ← taihi

先に消えるほうを避難させてから上書きする、という3行です。この3行は入替えの定型なので、順番ごと覚えてしまって構いません。逆に、退避用の変数がない選択肢は、それだけで誤りだと判断できます。

詰める操作

もう1つの定番がシフトです。途中の要素を取り除いて、後ろを1つずつ前へ詰める操作です。

考え方は単純で、data[i] に data[i + 1] を入れることを繰り返します。ただし、ここに境界の問題が出ます。

for (i を k から dataの要素数 - 1 まで 1 ずつ増やす) data[i] ← data[i + 1] endfor

終了値が dataの要素数 ではなく dataの要素数 - 1 になっています。もし要素数まで回すと、最後の周で data[要素数 + 1] を読むことになり、配列の外に出てしまいます。1つ先を見るループは1つ手前で止める、という決まりです。

前回の累積和では、1つ前を見るので開始値を 2 にしました。今回は1つ先を見るので終了値を 1 減らします。向きが違うだけで、はみ出さないという理由は同じです。

詰める向きに注意する

詰める処理は、前から順に進めます。後ろから進めると、まだ動かしていない値を先に上書きしてしまい、同じ値が並ぶ結果になります。逆に、要素を後ろへずらして空きを作る挿入の処理は、後ろから進めます。

どちらの向きが正しいかは、暗記しなくても判断できます。これから読む場所を、先に書き潰していないかを1周ぶんだけ確かめれば分かります。

空きを作る挿入の形

参考までに、逆向きのシフトも見ておきます。k 番目に新しい値を割り込ませたいときは、k 番目から末尾までを1つずつ後ろへずらします。

for (i を dataの要素数 から k + 1 まで 1 ずつ減らす) data[i] ← data[i - 1] endfor data[k] ← atarashiiAtai

1 ずつ減らす と書いて後ろから回している点と、data[i - 1] と1つ前を見ている点が、詰める処理との違いです。後ろから回すので、書き込む先はいつもまだ読んでいない場所になります。ここでも、読む前に書き潰していないかという同じ基準で向きを決めています。

交換の回数を問われることもある

設問では、入れ替えが何回起きたかを答えさせる形もあります。このときは、退避の行を通った回数を数えます。表を作るときに、taihi の列が変わった回数を数えておくと、あとから設問に答えられます。整列の章では、比較の回数と交換の回数を別々に問われるので、今のうちに数える習慣を付けておいてください。

今回のトレースでは、k 番目の要素を取り除いて後ろを詰め、空いた末尾に取り除いた値を置きます。data の初期値は {3, 1, 4, 1, 5}、k は 2 です。

課題

  1. 各行を実行したあとの値を入れる
  2. 値が変わらない変数はそのままの値を入れる
  3. 配列は {3, 1, 4, 1, 5} の形で5つとも書く

ヒント

1 / 10 行目のトレース

1○整数型の配列: sakujo(整数型の配列: data, 整数型: k)
2 整数型: i, taihi
3 taihi ← data[k]
4 for (i を k から dataの要素数 - 1 まで 1 ずつ増やす)
5   data[i] ← data[i + 1]
6 endfor
7 data[dataの要素数] ← taihi
8 return data
実行した行iktaihidata
実行前—2—{3, 1, 4, 1, 5}
3 行目

3 行目を実行したあとの値を入れてください。変わらない変数は、 そのままの値を入れます。まだ値が入っていない変数は「—」と入れます。