JavaScriptの初心者ソートアルゴリズム：バブル、選択、挿入ソート

投稿日: 2022-04-20 2022-10-10
タグ: javascript

データセットをすべて整理しておくと、管理と検索にかかる時間とリソースが増えるだけです。データが並べ替えられているかどうかは、使用できる検索方法に直接影響し、バイナリ検索のように、100万回の操作と10回の検索の違いを意味します。

簡単にするために、数値の配列を最小から最大にソートすることにのみ焦点を当てますが、これらのアルゴリズムは他のソート目標に合わせて簡単に変更できます。特定の実装は大きく異なる可能性があるため、これらはより一般的な概念とパターンであり、データを並べ替えるための「ハウツー」ではないことに注意してください。ただし、最終的にはこれらのパターンに概念的に似ている可能性があります。

これが50個のランダムな数字の練習配列です。

const unsortedArr = [31, 27, 28, 42, 13, 8, 11, 30, 17, 41, 15, 43, 1, 36, 9, 16, 20, 35, 48, 37, 7, 26, 34, 21, 22, 6, 29, 32, 49, 10, 12, 19, 24, 38, 5, 14, 44, 40, 3, 50, 46, 25, 18, 33, 47, 4, 45, 39, 23, 2];

前提条件

Big O Notation のレンズを通してすべてを見ていくので、時間の経過とともに複雑さがどのように増大するかを理解することは非常に役立ちます。

バブルソート

これは、並べ替え方法の「Hello World」であり、クレイジーなことは何もありませんが、仕事は終わります。

配列内の各アイテムについて、次のアイテムが大きいかどうかを確認し、次に配列内のインデックスを交換するかどうかを確認します。ソートされた数値の再比較を避けるために、配列の後ろから開始し、別の数値から開始します for loop 前の番号を取得します。このようにして、すべての最大値が最終的に蓄積または「バブルアップ」します。

VisuAlgo.netのおかげでグラフィック/アニメーション

私たちのバージョンはアニメーションとは逆に機能しますが、十分に近いです。

const bubble = arr => {
  const swap = (list, a, b) => [list[a], list[b]] = [list[b], list[a]];

  for (let i = arr.length; i > 0; i--) {
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) swap(arr, j, j + 1);
    };
  };

  return arr;
};

console.log(bubble(unsortedArr));

選択ソート

選択ソートはバブルソートの反対のように機能しますが、バブルソートはすべての最大値を最後にプッシュし、最小値を最初にプッシュします。

配列をループするたびに、最小値を選択します。それよりも低い値が見つかった場合は、それが新しい最小値になります。ループが完了すると、その最小値を取得してアレイの先頭に配置してから、ループを再開します。このようにして、配列全体がソートされるまで、各反復の最小値が前面にスタックされます。

VisuAlgo.netのおかげでグラフィック/アニメーション

const selection = arr => {
  const swap = (list, a, b) => [list[a], list[b]] = [list[b], list[a]];

  arr.forEach((item, i) => {
    let min = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[min]) min = j;
    };
    swap(arr, i, min);
  });

  return arr;
};

console.log(selection(unsortedArr));

挿入ソート

私の個人的なお気に入りであり、3つの中で最もパフォーマンスの高い挿入ソートは、手作業で何かをソートする方法に似ています。

配列は、並べ替えられた部分と並べ替えられていない部分の2つの部分と見なされ、新しい値が見つかるたびにループバックして、並べ替えられた半分の場所を見つけます。追加するたびに、ソートされたグループは配列全体になるまで大きくなります。

VisuAlgo.netのおかげでグラフィック/アニメーション

const insertion = arr => {
  arr.forEach((item, i) => {
    let num = arr[i];
    let j;

    for (j = i - 1; j >= 0 && arr[j] > num; j--) {
      arr[j + 1] = arr[j];
    };
    arr[j + 1] = num;
  });

  return arr;
};

console.log(insertion(unsortedArr));

比較

アルゴリズムの比較にBigONotationを使用する場合の問題の1つは、最悪のシナリオに基づいていることです。これは、アルゴリズム全体で同じであり、アルゴリズムが等しいという誤った錯覚を与える可能性があります。バブル、選択、挿入の並べ替えはすべてO（n ^ 2）ですが、平均的なシナリオや最良のシナリオ、またはデータ構造によってどのように変化するかについてはあまりわかりません。

挿入ソートは毎回勝ちます。また、開始する前に配列全体を用意する必要がないという利点もあります。これにより、データが入ってくるときにリアルタイムで並べ替えることができます。

データがすでにどのように編成されているかを検討する前に、どのアルゴリズムが「最適」であるかを判断するべきではないため、これを覚えておいてください。

結論

これらの3つは、大量のデータを効率的に並べ替えるのに最適なソリューションとはほど遠いものですが、圧倒的な海に足を踏み入れるのに最も直感的な方法の1つです。 🌊

getdocs

13036