配列アルゴリズム演習
まず結論
科目Bの最終仕上げとして、配列操作の典型問題（回転・マージ・重複チェック・逆順）をトレース表を使って解く練習をします。問題文を読んでトレース表を書き、選択肢と照合する一連の流れを体で覚えましょう。
配列操作の視覚イメージ
左回転（rotateLeft）
1
2
3
4
5
→
2
3
4
5
1
先頭をtmpに退避 → 左シフト → tmpを末尾へ
逆順（reverse）
1
2
3
4
5
→
5
4
3
2
1
i=1〜n÷2 で a[i] ↔ a[n+1-i] を交換
マージ（2つのソート済み配列を統合）
a[]
1
3
5
+
b[]
2
4
6
→
c[]
1
2
3
4
5
6
小さい方を順に選んで c[] に追加
重複チェック（O(n²) 全ペア比較）
3
1
4
1
5
a[2]=1 = a[4]=1 → 真（重複発見）
発見した瞬間にreturn → 最良O(1)
演習1：配列の回転（ローテーション）
// 配列を左に1つシフト（先頭を末尾に移動）
手続き rotateLeft(a, n)
tmp ← a[1] // 先頭を退避
i を 1 から n-1 まで繰り返す
a[i] ← a[i+1] // 1つずつ左にずらす
繰り返し終わり
a[n] ← tmp // 退避した先頭を末尾に
手続き終わり
| 操作 | 配列の状態 |
|---|---|
| 初期（n=5） | [1, 2, 3, 4, 5] |
| tmp ← a[1] | tmp=1, 配列変化なし |
| i=1: a[1]←a[2] | [2, 2, 3, 4, 5] |
| i=2: a[2]←a[3] | [2, 3, 3, 4, 5] |
| i=3: a[3]←a[4] | [2, 3, 4, 4, 5] |
| i=4: a[4]←a[5] | [2, 3, 4, 5, 5] |
| a[5] ← tmp(=1) | [2, 3, 4, 5, 1] |
演習2：配列の重複チェック
// 配列に重複した要素があるかどうかを確認
手続き hasDuplicate(a, n)
i を 1 から n-1 まで繰り返す
j を i+1 から n まで繰り返す
もし a[i] = a[j] ならば
真 を返す // 重複発見
もし終わり
繰り返し終わり
繰り返し終わり
偽 を返す // 重複なし
手続き終わり
ポイント：i=1からn-1まで、j=i+1からnまでの二重ループで全ペアを比較。計算量はO(n²)。同じ要素が見つかった瞬間に「真」を返して終了（早期リターン）。
演習3：マージ（2つのソート済み配列を統合）
// a[1..m]とb[1..n]（両方昇順）をマージしてc[]に格納
i ← 1 // aのポインタ
j ← 1 // bのポインタ
k ← 1 // cのポインタ
i が m 以下 かつ j が n 以下 の間, 繰り返す
もし a[i] ≦ b[j] ならば
c[k] ← a[i], i ← i+1
そうでなければ
c[k] ← b[j], j ← j+1
もし終わり
k ← k+1
| i | j | 比較 | c[]へ追加 |
|---|---|---|---|
| 1 | 1 | a[1]=1 ≦ b[1]=2 | c[1]=1、i→2 |
| 2 | 1 | a[2]=3 > b[1]=2 | c[2]=2、j→2 |
| 2 | 2 | a[2]=3 ≦ b[2]=4 | c[3]=3、i→3 |
| 3 | 2 | a[3]=5 > b[2]=4 | c[4]=4、j→3 |
a=[1,3,5], b=[2,4,6]のマージ結果は[1,2,3,4,5,6]。マージソートの核心操作。
配列操作パターンまとめ
| 操作 | コードの特徴 | 計算量 |
|---|---|---|
| 最大/最小検索 | 1変数maxを更新しながら1重ループ | O(n) |
| 合計・平均 | sum変数を加算しながら1重ループ | O(n) |
| 線形探索 | 条件一致で即return | O(n) |
| 二分探索 | left/right/midで範囲を半分に | O(log n) |
| バブルソート | 2重ループ・隣接交換 | O(n²) |
| 選択ソート | 2重ループ・最小値と先頭を交換 | O(n²) |
| 重複チェック | 2重ループ・全ペア比較 | O(n²) |
| 配列回転 | tmp退避・シフト・tmpを末尾/先頭に | O(n) |
🎯 試験合格に向けた最終チェックリスト
- トレース表を30秒以内に書き始められる（変数抽出が速い）
- ループの回数を正確に数えられる（i を A から B → B-A+1回）
- インデックスが0始まりか1始まりかを毎回確認する習慣がある
- 再帰の呼び出し順と戻り順が逆だと理解している
- バブルソートと選択ソートの違いが即答できる
⚠️ 直前の最終注意事項
- 「試験当日のコツ：問題文を先に読んで『何を求めているか』を把握してからコードを読む」
- 「詰まったらスキップ。時間を無駄にしない」
- 「最後の5分で見直し。マークミスや解答漏れを確認」
✍️ 確認クイズ（総合問題）
Q1. 配列[4, 1, 3, 2]に対してrotateLeft（左に1つ回転）を実行した結果はどれか。
✅ 正解は②。左回転は先頭要素(4)を末尾に移動し、残りを1つずつ前にずらす。[4,1,3,2]→先頭4を退避→[1,3,2,_]→末尾に4→[1,3,2,4]。
Q2. hasDuplicate([3, 1, 4, 1, 5])を実行した結果はどれか。
✅ 正解は①。配列に1が2箇所（a[2]とa[4]）あるため重複あり。i=2,j=4のとき a[2]=1=a[4]=1 で真を返します。
Q3. マージアルゴリズムの前提条件として正しいものはどれか。
✅ 正解は②。マージは2つのソート済み配列を統合するアルゴリズム。前提としてどちらの配列もソートされている必要があります（マージソートでも利用される操作）。配列の長さは異なっていても問題ありません。
Q4. 配列[1,2,3,4,5]の逆順（[5,4,3,2,1]）を作るアルゴリズムとして正しいものはどれか。
✅ 正解は②。配列の逆順は先頭と末尾のペアを順に交換するO(n)のアルゴリズムが効率的です。n=5の場合：i=1でa[1]↔a[5]（1↔5）、i=2でa[2]↔a[4]（2↔4）、i=2まで（n÷2=2）で完了。中央のa[3]は変化なし。
Q5. 重複チェックアルゴリズム（hasDuplicate）の計算量はどれか。
✅ 正解は②。hasDuplicateは外ループi=1〜n-1、内ループj=i+1〜nの二重ループで全ペア(i,j)を比較します。比較回数はn*(n-1)/2回＝O(n²)。ただし重複が見つかった瞬間に即returnするため、最良計算量はO(1)（先頭2要素が重複）となります。最悪（重複なし）がO(n²)です。
Sponsor Link