情報Ⅰ コース
✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ 14 15 16 17 18 19 20
14 STEP 14 / 21

プログラム表記⑤ 関数・探索とソート

⏱ 約40分 やってみよう 3 クイズ 5

🎯 このレッスンで学ぶこと

  • プログラムに出てくる関数(要素数(Data) など)の読み方がわかります。
  • 線形探索と二分探索の仕組みと、比較回数の違いがわかります。
  • 選択ソートとバブルソートで、配列が並べ替わる過程をトレースできるようになります。
  • レッスン10〜13の文法を組み合わせた、長めのプログラムが読めるようになります。
💡 この回はシリーズの総仕上げです。新しい文法はほとんどありません。代入・条件分岐・繰り返し・配列を組み合わせたプログラムを読みます。 プログラムが長くなっても、やることは同じ——トレース表を書いて1行ずつ追うだけです。

🧰 関数:値を渡すと結果を返してくれる命令

関数とは、値を渡すと、決まった処理をして結果を返してくれる命令のまとまりです。 かっこの中に渡す値を引数(ひきすう)、返ってくる結果を戻り値(もどりち)といいます。

関数の例働き例戻り値
要素数(配列)配列の要素の個数を返す要素数([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 に代入する」と読みます。関数の部分は、戻り値に置きかえて読むのがコツです。

    📝 JavaScript では:要素数は 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ページ目から順番に見る人はいませんね。真ん中あたりを開いて「もっと後ろ」「もっと前」と絞り込みます。これをプログラムにしたのが二分探索です。

      1. 探す範囲の左端を lo、右端を hi とする(最初は配列全体)
      2. 真ん中の位置 mid = (hi + lo) ÷ 2 を求める(÷ は商なので、割り切れなくても整数になる)
      3. Data[mid] が探す値なら終わり。探す値より小さければ右半分(lo = mid + 1)、大きければ左半分(hi = mid - 1)に絞る
      4. 範囲がなくなる(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 の結果が表示されます。

        実行する前に、次のトレース表を自分で書いてみてください。

        回lohimidData[mid]判断
        1回目07(7 + 0) ÷ 2 = 31515 < 56 → 右半分へ(lo = 4)
        2回目47(7 + 4) ÷ 2 = 54242 < 56 → 右半分へ(lo = 6)
        3回目67(7 + 6) ÷ 2 = 656見つかった(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周目010(添字1)[10, 29, 14, 37, 13]
          2周目113(添字4)[10, 13, 14, 37, 29]
          3周目214(添字2・自分自身)[10, 13, 14, 37, 29]
          4周目329(添字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行で行う

            ⚡ JavaScript で同じことをやってみよう

            本物のプログラミング言語では、探索やソートのような処理を「関数」として自分で作り、名前をつけて何度でも使えます。JavaScript で関数を作ってみましょう。

            JavaScriptコース レッスン5「関数」へ →

            ✅ このレッスンが終わったら

            プログラム表記のシリーズはこれで完了です。次は、乱数を使って現実の出来事をコンピュータで再現する「モデル化とシミュレーション」です。

            次のレッスン: モデル化とシミュレーション →

            このレッスンは役に立ちましたか?

            目次