プログラム表記⑤ 関数・探索とソート
🎯 このレッスンで学ぶこと
- プログラムに出てくる関数(
要素数(Data)など)の読み方がわかります。 - 線形探索と二分探索の仕組みと、比較回数の違いがわかります。
- 選択ソートとバブルソートで、配列が並べ替わる過程をトレースできるようになります。
- レッスン10〜13の文法を組み合わせた、長めのプログラムが読めるようになります。
🧰 関数:値を渡すと結果を返してくれる命令
関数とは、値を渡すと、決まった処理をして結果を返してくれる命令のまとまりです。 かっこの中に渡す値を引数(ひきすう)、返ってくる結果を戻り値(もどりち)といいます。
| 関数の例 | 働き | 例 | 戻り値 |
|---|---|---|---|
要素数(配列) | 配列の要素の個数を返す | 要素数([3, 9, 4]) | 3 |
整数(x) | x の小数点以下を切り捨てた整数を返す | 整数(7.8) | 7 |
乱数(m, n) | m 以上 n 以下の整数をランダムに1つ返す | 乱数(1, 6) | 1〜6 のどれか |
関数の働きは、試験では問題文で説明されます。「関数 ○○ は、引数として配列を受け取り、その要素の個数を返す」のように書かれているので、 その説明どおりに「この値を渡すと、この値が返ってくる」と読めば大丈夫です。関数の名前や働きを暗記しておく必要はありません。
ここで紹介した3つは、この実行環境で実際に使える関数です。動かして確かめてみましょう。
▶ 動かしてみよう:関数の戻り値
「1行ずつ実行」を押すたびに1手順ずつ進み、いま実行した行が光ります。
📦 変数の中身
| まだ何も入っていません |
🖥 表示された内容
📝 トレース表(実行した順の記録)
| 手順 | 行 | 起きたこと |
|---|
⚡ 同じ処理を JavaScript で書くと?
試験の表記と本物のプログラミング言語は、書き方が少し違うだけで考え方は同じです。
let Data = [3, 9, 4];
let n = Data.length;
let x = Math.floor(7.8);
let saikoro = Math.floor(Math.random() * 6) + 1;
console.log("要素数:" + n + " 整数:" + x + " サイコロ:" + saikoro); 💡 動かすには:コードをコピーし、ブラウザで F12(Mac は ⌘+⌥+I)を押して開く「コンソール」に貼り付けて Enter。console.log の結果が表示されます。
n は 3、x は 7 です。saikoro は実行するたびに変わります(「↺ 最初から」で何度か実行してみましょう)。
n = 要素数(Data) は「要素数(Data) の戻り値(3)を n に代入する」と読みます。関数の部分は、戻り値に置きかえて読むのがコツです。
Data.length、切り捨ては Math.floor()、乱数は Math.random() を使います。
本物のプログラミング言語では、関数を自分で作ることもできます(JavaScriptコースのレッスン5で学べます)。
🔍 線形探索:先頭から順番に探す
配列の中から目的の値を探すことを探索といいます。一番素直な方法は、先頭から1つずつ順番に比べていく方法で、これを線形探索(逐次探索)といいます。
▶ 動かしてみよう:線形探索で 27 を探す
「1行ずつ実行」を押すたびに1手順ずつ進み、いま実行した行が光ります。
📦 変数の中身
| まだ何も入っていません |
🖥 表示された内容
📝 トレース表(実行した順の記録)
| 手順 | 行 | 起きたこと |
|---|
⚡ 同じ処理を JavaScript で書くと?
試験の表記と本物のプログラミング言語は、書き方が少し違うだけで考え方は同じです。
let Data = [15, 3, 42, 8, 27, 11];
let atai = 27;
let basho = -1;
let hikaku = 0;
let i = 0;
while (i < Data.length && basho == -1) {
hikaku = hikaku + 1;
if (Data[i] == atai) {
basho = i;
}
i = i + 1;
}
console.log("添字" + basho + "で見つかった。比較" + hikaku + "回"); 💡 動かすには:コードをコピーし、ブラウザで F12(Mac は ⌘+⌥+I)を押して開く「コンソール」に貼り付けて Enter。console.log の結果が表示されます。
basho = -1は「まだ見つかっていない」という目印です(-1 という添字は存在しないので、目印に使えます)。- 繰り返しの条件は「まだ配列の中(i < 要素数)かつ まだ見つかっていない(basho == -1)」です。見つかった時点で basho が -1 でなくなり、繰り返しが終わります。
- 27 は添字4(5番目)にあるので、比較は 5回 です。
やってみよう:「✏️ 書き換える」で atai = 27 を atai = 50(配列にない値)に変えて実行してみましょう。
最後まで比べても見つからず、basho は -1 のまま、比較は6回(要素数と同じ)になります。
✂️ 二分探索:真ん中と比べて半分に絞る
辞書で単語を引くとき、1ページ目から順番に見る人はいませんね。真ん中あたりを開いて「もっと後ろ」「もっと前」と絞り込みます。これをプログラムにしたのが二分探索です。
- 探す範囲の左端を lo、右端を hi とする(最初は配列全体)
- 真ん中の位置
mid = (hi + lo) ÷ 2を求める(÷ は商なので、割り切れなくても整数になる) - Data[mid] が探す値なら終わり。探す値より小さければ右半分(lo = mid + 1)、大きければ左半分(hi = mid - 1)に絞る
- 範囲がなくなる(lo > hi)まで 2〜3 をくり返す
▶ 予想してから実行:二分探索で 56 を探す
「1行ずつ実行」を押すたびに1手順ずつ進み、いま実行した行が光ります。
📦 変数の中身
| まだ何も入っていません |
🖥 表示された内容
📝 トレース表(実行した順の記録)
| 手順 | 行 | 起きたこと |
|---|
⚡ 同じ処理を JavaScript で書くと?
試験の表記と本物のプログラミング言語は、書き方が少し違うだけで考え方は同じです。
let Data = [3, 8, 11, 15, 27, 42, 56, 70];
let atai = 56;
let lo = 0;
let hi = Data.length - 1;
let basho = -1;
let hikaku = 0;
while (lo <= hi && basho == -1) {
let mid = Math.floor((hi + lo) / 2);
hikaku = hikaku + 1;
if (Data[mid] == atai) {
basho = mid;
} else if (Data[mid] < atai) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
console.log("添字" + basho + "で見つかった。比較" + hikaku + "回"); 💡 動かすには:コードをコピーし、ブラウザで F12(Mac は ⌘+⌥+I)を押して開く「コンソール」に貼り付けて Enter。console.log の結果が表示されます。
実行する前に、次のトレース表を自分で書いてみてください。
| 回 | lo | hi | mid | Data[mid] | 判断 |
|---|---|---|---|---|---|
| 1回目 | 0 | 7 | (7 + 0) ÷ 2 = 3 | 15 | 15 < 56 → 右半分へ(lo = 4) |
| 2回目 | 4 | 7 | (7 + 4) ÷ 2 = 5 | 42 | 42 < 56 → 右半分へ(lo = 6) |
| 3回目 | 6 | 7 | (7 + 6) ÷ 2 = 6 | 56 | 見つかった(basho = 6) |
二分探索では 3回の比較で見つかりました。同じ配列を線形探索で先頭から探すと、56 は7番目なので 7回 かかります。
⚖️ 比較回数の違い
線形探索は1回の比較で候補が1つしか減りませんが、二分探索は1回の比較で候補が約半分になります。データが多いほど、この差は大きくなります。
| データの個数 | 線形探索(最大の比較回数) | 二分探索(最大の比較回数) |
|---|---|---|
| 8個 | 8回 | 4回 |
| 1,000個 | 1,000回 | 10回 |
| 100万個 | 100万回 | 20回 |
ただし二分探索は、前もって整列しておく必要があるのが弱点です。そこで必要になるのが、次の「ソート」です。
🔢 ソートの基本:値の入れ替え
配列を小さい順(昇順)や大きい順(降順)に並べ替えることをソート(整列)といいます。ソートは「2つの要素を入れ替える」ことのくり返しです。 入れ替えには、レッスン10で学んだ一時的な変数 tmp を使います。
tmp = Data[i]
Data[i] = Data[j]
Data[j] = tmp tmp がないと、2行目で Data[i] の元の値が消えてしまいます。この3行の形を見たら「入れ替えだ」と気づけるようにしておきましょう。
👑 選択ソート:一番小さいものを選んで前へ
選択ソートは、「まだ並べていない部分から一番小さい値を選び、その部分の先頭と入れ替える」をくり返す方法です。
▶ 動かしてみよう:選択ソート(1周ごとに表示)
「1行ずつ実行」を押すたびに1手順ずつ進み、いま実行した行が光ります。
📦 変数の中身
| まだ何も入っていません |
🖥 表示された内容
📝 トレース表(実行した順の記録)
| 手順 | 行 | 起きたこと |
|---|
⚡ 同じ処理を JavaScript で書くと?
試験の表記と本物のプログラミング言語は、書き方が少し違うだけで考え方は同じです。
let Data = [29, 10, 14, 37, 13];
let n = Data.length;
for (let i = 0; i <= n - 2; i = i + 1) {
let saisho = i;
for (let j = i + 1; j <= n - 1; j = j + 1) {
if (Data[j] < Data[saisho]) {
saisho = j;
}
}
let tmp = Data[i];
Data[i] = Data[saisho];
Data[saisho] = tmp;
console.log((i + 1) + "周目: [" + Data.join(", ") + "]");
} 💡 動かすには:コードをコピーし、ブラウザで F12(Mac は ⌘+⌥+I)を押して開く「コンソール」に貼り付けて Enter。console.log の結果が表示されます。
| 周 | i | 選ばれた最小値(添字 saisho) | 入れ替え後の Data |
|---|---|---|---|
| はじめ | — | — | [29, 10, 14, 37, 13] |
| 1周目 | 0 | 10(添字1) | [10, 29, 14, 37, 13] |
| 2周目 | 1 | 13(添字4) | [10, 13, 14, 37, 29] |
| 3周目 | 2 | 14(添字2・自分自身) | [10, 13, 14, 37, 29] |
| 4周目 | 3 | 29(添字4) | [10, 13, 14, 29, 37] |
1周ごとに、前から順に1つずつ位置が確定していきます。最後の1つは自動的に一番大きい値になるので、外側の繰り返しは n - 2 までで足ります。
内側の繰り返し(j)は、レッスン13の「最小値を求める」とまったく同じ形です。
🫧 バブルソート:となり同士を比べて入れ替える
バブルソートは、「となり同士を比べて、順番が逆なら入れ替える」を左から右へくり返す方法です。 1周すると、一番大きい値が泡(バブル)のように右端まで浮かび上がります。
▶ 予想してから実行:バブルソート(1周ごとに表示)
「1行ずつ実行」を押すたびに1手順ずつ進み、いま実行した行が光ります。
📦 変数の中身
| まだ何も入っていません |
🖥 表示された内容
📝 トレース表(実行した順の記録)
| 手順 | 行 | 起きたこと |
|---|
⚡ 同じ処理を JavaScript で書くと?
試験の表記と本物のプログラミング言語は、書き方が少し違うだけで考え方は同じです。
let Data = [5, 3, 8, 1];
let n = Data.length;
for (let i = 0; i <= n - 2; i = i + 1) {
for (let j = 0; j <= n - 2 - i; j = j + 1) {
if (Data[j] > Data[j + 1]) {
let tmp = Data[j];
Data[j] = Data[j + 1];
Data[j + 1] = tmp;
}
}
console.log((i + 1) + "周目: [" + Data.join(", ") + "]");
} 💡 動かすには:コードをコピーし、ブラウザで F12(Mac は ⌘+⌥+I)を押して開く「コンソール」に貼り付けて Enter。console.log の結果が表示されます。
| 周 | 比べるペア(j と j + 1) | 周の終わりの Data | 確定した値 |
|---|---|---|---|
| はじめ | — | [5, 3, 8, 1] | — |
| 1周目 | 5と3(交換)→ 5と8 → 8と1(交換) | [3, 5, 1, 8] | 8 |
| 2周目 | 3と5 → 5と1(交換) | [3, 1, 5, 8] | 5 |
| 3周目 | 3と1(交換) | [1, 3, 5, 8] | 3 |
右端から順に値が確定していくので、内側の繰り返しの終わりは n - 2 - i と、周を重ねるごとに短くなっています。比較の回数は 3 + 2 + 1 = 6回です。
| 選択ソート | バブルソート | |
|---|---|---|
| 何をくり返す? | 残りから最小値を選び、先頭と入れ替える | となり同士を比べ、逆なら入れ替える |
| どこから確定する? | 左端(小さい値)から | 右端(大きい値)から |
| 入れ替えの回数 | 1周に1回 | 1周に何回も起こりうる |
📊 見てみよう:バブルソートを棒グラフで
「1手進む」を押すたびに、となり同士を1回比べます。比べている2本は色が変わり、順番が逆なら入れ替わります。右端から色が変わった棒が「確定した値」です。
📝 定期テストではこう出る
- 過程を答える:「[4, 2, 5, 1] をバブルソートしたとき、1周目が終わった配列は?」(答え [2, 4, 1, 5])
- 二分探索の mid:「lo = 0、hi = 9 のときの mid は?」(答え (9 + 0) ÷ 2 = 4)
- 比較回数:線形探索と二分探索で、ある値を見つけるまでの比較回数を答える
- 用語と特徴:「二分探索を使うための条件は?」(答え:データが整列済みであること)
🎓 共通テストではこう出る
共通テストでは、探索やソートが名前を伏せた形で出ることもあります。「このプログラムは何をしているか」を読み取れることが大切です。
- 空欄補充:二分探索の
lo = mid + 1とhi = mid - 1のどちらが入るか、ソートの比較の向き(> か < か)、入れ替えの式など - トレース:「ソートの2周目が終わったときの配列」「探索が終わるまでの比較回数」を答える
- プログラムの目的:「このプログラムは配列を大きい順に並べ替える」のように、全体の働きを選ぶ
問題文で説明される関数(たとえば「配列の要素数を返す関数」)は、説明をそのまま信じて戻り値に置きかえて読みましょう。長いプログラムでも、トレース表を書けば必ず読めます。
📖 もっと詳しく:ソートと探索のアルゴリズム解説 / 共通テストのプログラム問題の解き方 / 定期テスト対策
✏️ もっと練習:情報Ⅰ トレース練習(表記が少し違います。← は = と同じ意味で、配列の添字が1から始まります)
📝 まとめ
- ✅ 関数は値(引数)を渡すと結果(戻り値)を返す。働きは試験の問題文で説明される
- ✅ 線形探索は先頭から順に比べる。見つからなければ要素数と同じ回数比べる
- ✅ 二分探索は整列済みの配列で、mid = (hi + lo) ÷ 2 と比べて範囲を半分に絞る
- ✅ 1回の比較で、線形探索は候補が1つ、二分探索は約半分減る
- ✅ 選択ソートは最小値を選んで前へ(左から確定)、バブルソートはとなり同士を交換(右から確定)
- ✅ 入れ替えは tmp を使った3行で行う
このレッスンは役に立ちましたか?
フィードバックありがとうございます!