ソート1：バブルソート、選択ソート、挿入ソート

選択ソートは、10個の値のリストならどんなものでも、はじめがばらばらでもすでに整列していても、ちょうど45回比較します。

順番に並べる

ソート（整列）とは、リストの値が小さいものから大きいものへ（あるいは名前順、日付順、値段順など、比べられるどんな順でも）並ぶように並べかえることです。コンピューターがする仕事の中でも特によくあるものです。スマートフォンの連絡先、関連の高い順に並んだ検索結果、日付順に並べたスプレッドシートの列などがそうです。ソートは、ほかの仕事も楽にします。前のユニットで見たように、整列したリストは二分探索で探せますし、整列したリストでは重複した値が隣どうしに並びます。

このユニットでは3つの簡単な方法を扱います。どれも2つの値を一度に比べ、同じリストの中で値を動かして進めます。短く書けて追いやすいのですが、3つとも長いリストでは急に遅くなります。なぜ遅くなるのかを見ておくことが、次のユニットのもっと速い方法へのいちばんの準備になります。ここではずっと、比較（「この値はあの値より大きいか？」と問うこと）と交換（2つの値を入れかえること）の2つを数えます。

バブルソート：順番が逆の隣どうしを交換する

バブルソートは、リストにそって隣どうしの組を順に比べていきます。左のほうが大きければ、2つを交換します。1回の走査が終わると、最大の値が泡が浮かぶように一歩ずつ右端まで運ばれ、もう動かす必要はなくなります。次の走査は1つ手前で止められます。よくある改良は、交換が1回もない走査に気づくことです。それはすべてがもう順に並んでいるという意味なので、ソートを早めに終えられます。

リスト [5, 1, 4, 2, 8] で追ってみましょう。1回目の走査では、5と1（交換）、5と4（交換）、5と2（交換）、5と8（そのまま）を比べます。リストは [1, 4, 2, 5, 8] になり、8は正しい位置に来ました。2回目の走査では1と4、4と2（交換）、4と5を比べて、[1, 2, 4, 5, 8] になります。3回目の走査では1と2、次に2と4を比べ、交換がないので止まります。合計は比較 4 + 3 + 2 = 9 回、交換4回です。

function bubbleSort(a) {
  for (let pass = 0; pass < a.length - 1; pass++) {
    let swapped = false;
    for (let j = 0; j < a.length - 1 - pass; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];  // 交換
        swapped = true;
      }
    }
    if (!swapped) break;  // 整列済み
  }
  return a;
}

選択ソート：最小のものを見つけて次に置く

選択ソートは、多くの人が手持ちのトランプを並べるやり方と同じです。リスト全体から最小の値を探し、それを先頭の位置と交換します。次に残りから最小の値を探して2番目の位置と交換し、これを続けます。[5, 1, 4, 2, 8] では、1回目の探索で1を見つけて5と交換し、2回目で2を見つけて5と交換します。最後の2回の探索では、4と5がもう正しい位置にあるとわかります。交換は2回だけですが、探索での比較は 4 + 3 + 2 + 1 = 10 回あります。

選択ソートは途中で止まりません。すでに整列したリストでも、最小の値を手にしていると確かめるために、残りの値をすべて調べなければなりません。n個の値では、比較の回数はいつも (n − 1) + (n − 2) + … + 1 = n(n − 1)/2 になります。10個なら45回、100個なら4,950回、1,000個なら499,500回です。強みは交換の少なさで、多くてもn − 1回です。値を動かすのに手間がかかるときには、これが効いてきます。

挿入ソート：新しい値を正しい位置へすべりこませる

挿入ソートは、リストの左側を整列した状態に保ち、それを1つずつ広げていきます。次の値を取り、隣の値が大きくなくなるまで、隣と交換しながら左へ動かします。するとその値は、整列した値の中で正しい位置に入ります。すでにほぼ整列したリストでは、新しい値はそれぞれ1〜2歩しか動かないので、挿入ソートはとても速くなります。[5, 1, 4, 2, 8] では、比較7回、交換4回です。

交換を数える：転倒

バブルソートと挿入ソートの交換の回数を予想する、うまい方法があります。転倒、つまりおたがいの順番が逆になっている値の組を数えるのです。[5, 1, 4, 2, 8] の転倒は (5, 1)、(5, 4)、(5, 2)、(4, 2) の全部で4つです。順番が逆の隣どうしを1回交換すると、転倒がちょうど1つ直り、新しい転倒はできません。だからどちらの方法も、交換はちょうど4回です。n個の値の逆順のリストでは、すべての組が転倒していて、転倒は n(n − 1)/2 個です。これが最悪の場合です。

各マスは 比較 / 交換 の回数です。例のリストは [5, 1, 4, 2, 8] です。ここでのバブルソートは、交換のない走査の後で止まる版です。

3つの方法には同じ弱点があります。最悪の場合、どれもほぼすべての値の組を比べ、比較は約 n²/2 回になります。リストを2倍にすると仕事量は4倍になります。リストが10倍なら仕事量は100倍です。数十個の値ならほとんど問題になりませんが、100万個ではお手上げです。次のユニットでは、ずっとうまいやり方を見ていきます。