演習: ソートアルゴリズム

9-a. バブルソートのトレース

配列 [4, 2, 7, 1, 3] に対してバブルソートを実行したとき、1パス目で行われる比較と交換をすべて書き出してください。1パス目終了時の配列の状態も答えてください。

ヒント

左から順に隣り合うペアを比較します。左のほうが大きければ交換し、そうでなければそのまま次のペアに進みます。

9-b. バブルソートの全パストレース

配列 [6, 3, 5, 1] に対してバブルソートを実行したとき、全パスの過程を表に書き出してください。

何パス目	結果
1	?
2	?
3	?

ヒント

本文 2-4. トレース と同じ方法です。各パスで隣り合うペアを左から順に比較・交換していきます。

9-c. 選択ソートのトレース

配列 [4, 2, 7, 1, 3] に対して選択ソートを実行したとき、全パスの過程を表に書き出してください。

何パス目	未ソート範囲	最小値	交換	結果
1	[4, 2, 7, 1, 3]	?	?	?
2	?	?	?	?
3	?	?	?	?
4	?	?	?	?

ヒント

本文 3-4. トレース と同じ方法です。未ソート範囲から最小値を見つけ、範囲の先頭と交換します。

9-d. バブルソートの出力予測

以下のコードの出力結果を予測してから実行してください。

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
    console.log(arr);
  }
}

bubbleSort([3, 1, 4, 2]);

ヒント

console.log は各パスの終了時に実行されます。パスごとの配列の状態を追ってください。

9-e. 穴埋め: 選択ソート

選択ソートの内側のループの条件が抜けています。/* ??? */ に入るコードを、選択肢から選んでください。

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i;

    for (let j = i + 1; j < arr.length; j++) {
      if (/* ??? */) {
        minIndex = j;
      }
    }

    if (minIndex !== i) {
      const temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }
}

選択肢:

• (ア) arr[j] < arr[i]
• (イ) arr[j] < arr[minIndex]
• (ウ) arr[j] > arr[minIndex]
• (エ) arr[minIndex] < arr[j]

ヒント

minIndex は「今のところ一番小さい要素のインデックス」です。新しい要素がそれより小さいかどうかを判定する必要があります。(ア) は minIndex ではなく i と比較しているので、途中で見つかった最小値が反映されません。

9-f. 降順のバブルソート

本文のバブルソートは昇順（小さい順）でした。これを降順（大きい順）に並べ替えるように変更してください。

const data = [5, 3, 8, 1, 4];

出力例:

[8, 5, 4, 3, 1]

ヒント

比較の向きを1箇所変えるだけです。

発展: 疑似言語

探索アルゴリズム (js-07) で扱った疑似言語で、ソートアルゴリズムも読む練習をします。記法は js-07 の発展セクションを参照してください。

9-g. 疑似言語でバブルソートを読む

以下の疑似言語プログラムは、バブルソートを表しています。配列 Data が {3, 1, 2} のとき、1パス目終了時の配列の状態を答えてください。

○bubbleSort(整数型の配列: Data)
  整数型: i, j, temp
  整数型: n ← 要素数(Data)

  for (iを1からn-1まで1ずつ増やす)
    for (jを1からn-iまで1ずつ増やす)
      if (Data[j] > Data[j + 1])
        temp ← Data[j]
        Data[j] ← Data[j + 1]
        Data[j + 1] ← temp
      endif
    endfor
  endfor

ヒント

添字が 1 から始まることに注意してください。i = 1 のとき、j は 1 から n - 1 = 2 まで進みます。Data[1] と Data[2] を比較し、次に Data[2] と Data[3] を比較します。

9-h. 疑似言語で選択ソートのトレース

以下の疑似言語プログラムについて、配列 Data が {5, 2, 4, 1, 3} のとき、2パス目終了時の配列の状態を答えてください。

○selectionSort(整数型の配列: Data)
  整数型: i, j, minIdx, temp
  整数型: n ← 要素数(Data)

  for (iを1からn-1まで1ずつ増やす)
    minIdx ← i
    for (jをi+1からnまで1ずつ増やす)
      if (Data[j] < Data[minIdx])
        minIdx ← j
      endif
    endfor
    if (minIdx ≠ i)
      temp ← Data[i]
      Data[i] ← Data[minIdx]
      Data[minIdx] ← temp
    endif
  endfor

ヒント

1パス目: 全体から最小値を探して先頭と交換します。2パス目: 2番目以降から最小値を探して2番目と交換します。添字は1始まりです。