9.ソートアルゴリズム

学習目標

• バブルソートの仕組みを理解し、トレースできる
• 選択ソートの仕組みを理解し、トレースできる
• 2つのソートアルゴリズムの共通点と違いを説明できる

---

1. ソート

配列の要素を小さい順（昇順）または大きい順（降順）に並べ替える処理を ソート と呼びます。二分探索 は「配列がソート済みであること」が前提でした。ソートはそのための手段であると同時に、プログラミングで最も基本的な処理の1つです。

代表的なソートアルゴリズムにバブルソートと選択ソートがあります。どちらもネストしたループを使います。

2. バブルソート

2-1. 考え方

バブルソート は、隣り合う2つの要素を比較して、順番が逆なら交換する処理を繰り返します。

配列 [5, 3, 8, 1, 4] を昇順に並べる場合の1パス目を見てみます。配列を左から右に走査しながら、隣り合うペアを比較し、左のほうが大きければ交換、そうでなければそのまま進みます。

開始
┌──┬──┬──┬──┬──┐
│　５│　３│　８│　１│　４│
└─▲┴──┴──┴──┴──┘
  j=0 ↓ (5,3) を交換
┌──┬──┬──┬──┬──┐
│　３│　５│　８│　１│　４│
└──┴─▲┴──┴──┴──┘
  j=1 ↓ (5,8) はそのまま
┌──┬──┬──┬──┬──┐
│　３│　５│　８│　１│　４│
└──┴──┴─▲┴──┴──┘
  j=2 ↓ (8,1) を交換
┌──┬──┬──┬──┬──┐
│　３│　５│　１│　８│　４│
└──┴──┴──┴─▲┴──┘
  j=3 ↓ (8,4) を交換
┌──┬──┬──┬──┬──┐
│　３│　５│　１│　４│　８│
└──┴──┴──┴──┴──┘

1パス目が終わると、最も大きい値（8）が末尾に移動しています。これを繰り返すと、2パス目では2番目に大きい値が末尾から2番目に、3パス目では3番目に大きい値が末尾から3番目に移動します。パスごとに大きい値が1つずつ末尾側で確定していきます。

2-2. 実装の方針

1. 隣り合う要素を比較・交換する

   左のほうが大きければ交換します。直接 a = b と書くと a の元の値が消えてしまうので、一時的な変数 temp に退避してから入れ替えます。

   対応するコード

   if (arr[j] > arr[j + 1]) {
     const temp = arr[j];
     arr[j] = arr[j + 1];
     arr[j + 1] = temp;
   }

2. 内側のループで1パス分を処理する

   この比較・交換を配列の先頭から末尾まで繰り返すのが1パス分です。

   対応するコード

   for (let j = 0; j < arr.length - 1 - i; j++) {
     // 比較・交換
   }

3. 外側のループでパスを繰り返す

   1パスごとに末尾側の要素が1つ確定するので、内側のループの範囲はパスごとに1つ短くなります。全体がソートされるまで続けます。

   対応するコード

   for (let i = 0; i < arr.length - 1; i++) {
     // 内側のループ
   }

2-3. 実装

関数版

sort.js

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;
      }
    }
  }
}

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

bubbleSort(data);
console.log(data);

[1, 3, 4, 5, 8]

関数を使わない版

sort.js

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

// パスを繰り返す
for (let i = 0; i < data.length - 1; i++) {
  // 1パス分: 隣り合うペアを比較
  for (let j = 0; j < data.length - 1 - i; j++) {
    if (data[j] > data[j + 1]) {
      // 順番が逆なら交換
      const temp = data[j];
      data[j] = data[j + 1];
      data[j + 1] = temp;
    }
  }
}

console.log(data);

[1, 3, 4, 5, 8]

外側のループ変数 i は何パス目かを表します（i = 0 が1パス目）。i が増えるたびに、内側のループ範囲が arr.length - 1 - i に短くなります。末尾側の i 個は既に確定しているので、比較する必要がないためです。

2-4. トレース

初期配列は [5, 3, 8, 1, 4] です。パスごとに比較・交換と結果を追います。

何パス目	比較・交換	結果
1	(5,3)交換 → (5,8)そのまま → (8,1)交換 → (8,4)交換	[3, 5, 1, 4, 8]
2	(3,5)そのまま → (5,1)交換 → (5,4)交換	[3, 1, 4, 5, 8]
3	(3,1)交換 → (3,4)そのまま	[1, 3, 4, 5, 8]
4	(1,3)そのまま	[1, 3, 4, 5, 8]

パスごとに比較回数が1つ減っていることが分かります。1パス目は4回、2パス目は3回、3パス目は2回、4パス目は1回です。

3. 選択ソート

3-1. 考え方

選択ソート は、「未ソートの範囲から最小値を見つけて、先頭と交換する」処理を繰り返します。

配列 [5, 3, 8, 1, 4] を昇順に並べる場合の最初の2パスを見てみます。1パス目では配列全体を走査して最小値 1 を見つけ、先頭の 5 と交換します。

1パス目 開始
┌──┬──┬──┬──┬──┐
│　５│　３│　８│　１│　４│
└──┴──┴──┴──┴──┘
   ↓ 最小値 1 を先頭の 5 と交換
┌──┬──┬──┬──┬──┐
│　１│　３│　８│　５│　４│
└──┴──┴──┴──┴──┘

これで先頭の位置が確定します。2パス目では残りの [3, 8, 5, 4] を走査して最小値 3 を見つけますが、既に正しい位置にあるので交換は不要です。

2パス目 開始
┌──┬──┬──┬──┬──┐
│　１│　３│　８│　５│　４│
└──┴──┴──┴──┴──┘
   ↓ 最小値 3 は既に正しい位置(交換不要)
┌──┬──┬──┬──┬──┐
│　１│　３│　８│　５│　４│
└──┴──┴──┴──┴──┘

バブルソートが「大きい値を末尾に送る」のに対して、選択ソートは「小さい値を先頭に持ってくる」という違いがあります。

3-2. 実装の方針

1. 未ソートの範囲から最小値を見つける

   配列から最大値を返す関数 と同じパターンで、比較の向きを逆にしたものです。

   対応するコード

   let minIndex = i;
   
   for (let j = i + 1; j < arr.length; j++) {
     if (arr[j] < arr[minIndex]) {
       minIndex = j;
     }
   }

2. 先頭と交換する

   最小値が見つかったら、i（未ソート範囲の先頭のインデックス）と minIndex の要素を交換します。

   対応するコード

   const temp = arr[i];
   arr[i] = arr[minIndex];
   arr[minIndex] = temp;

3. 外側のループでパスを繰り返す

   パスごとに未ソート範囲の開始位置が1つ右にずれるので、外側のループ変数 i が開始位置を表します。

   対応するコード

   for (let i = 0; i < arr.length - 1; i++) {
     // 最小値を見つけて先頭と交換
   }

3-3. 実装

関数版

sort.js

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 (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

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

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

selectionSort(data);
console.log(data);

[1, 3, 4, 5, 8]

関数を使わない版

sort.js

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

// パスを繰り返す
for (let i = 0; i < data.length - 1; i++) {
  let minIndex = i;

  // 未ソート範囲から最小値のインデックスを探す
  for (let j = i + 1; j < data.length; j++) {
    if (data[j] < data[minIndex]) {
      minIndex = j;
    }
  }

  // 最小値を先頭 (i) と交換
  if (minIndex !== i) {
    const temp = data[i];
    data[i] = data[minIndex];
    data[minIndex] = temp;
  }
}

console.log(data);

[1, 3, 4, 5, 8]

if (minIndex !== i) は、最小値が既に正しい位置にある場合に無駄な交換を省くためのチェックです。

3-4. トレース

配列 [5, 3, 8, 1, 4] のソート過程をパスごとに追います。

何パス目	未ソート範囲	最小値 → 交換	結果
1	[5, 3, 8, 1, 4]	1（インデックス3） → 5 と交換	[1, 3, 8, 5, 4]
2	[3, 8, 5, 4]	3（インデックス1） → 交換不要	[1, 3, 8, 5, 4]
3	[8, 5, 4]	4（インデックス4） → 8 と交換	[1, 3, 4, 5, 8]
4	[5, 8]	5（インデックス3） → 交換不要	[1, 3, 4, 5, 8]

バブルソートと異なり、選択ソートの交換回数は最大でもパス数と同じ（各パスで最大1回）です。比較回数は多いですが、交換回数が少ないという特徴があります。

4. 2つのソートの比較

	バブルソート	選択ソート
方法	隣り合う要素を比較・交換	最小値を見つけて先頭と交換
確定する方向	末尾から	先頭から
交換回数	多い（比較のたびに交換の可能性がある）	少ない（パスごとに最大1回）

どちらも要素数が増えると処理時間が急増するため、大量のデータには向きません。より高速なソートアルゴリズムも存在します。

Warning

bubbleSort(data) と selectionSort(data) は、引数として渡した配列の中身を並び替えます。呼び出した後の data は、ソート済みの並びになっています。

5. 演習

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