[JS] - Sorting Algorithm - Bubble Sort

📝 ソートアルゴリズムについて

の順序付け(順序付け)は、特定の順序でデータを再配置するプロセス

を意味する.

Bubbleソート、選択ソート、挿入ソート、クイックソート、マージソートなど.

単純(実装しやすい)が効率の悪いアルゴリズム
📌 Bubbleソート、選択ソート、挿入ソート

複雑だが効率的なアルゴリズム
📌 クイックソート、hipソート、マージソート、ベースソート

バブル整列(Bubble Sort)

最大値を気泡のように上に移動させるアルゴリズム.

2つの隣接する要素を検査してソートするアルゴリズム.

Bubbleソートは、重複するデータがある場合、データの位置が交換されないため、安定したソートです.

最初の資料と2番目の資料、2番目の資料と3番目の資料、3番目と4番目の資料...このようにしてデータをソートし、最後のデータと最後のデータを比較します.

第1ラウンドが完了すると、最大の資料が最後に移動するので、第2ラウンドでは、最後尾の資料がソートから除外され、第2ラウンドが完了すると、末尾から第2ラウンドまでの資料がソートから除外されます.

n第n回ソート終了後、後のn箇所のデータ決定

Big-O

最悪:O(n^2)ソートが1つもない場合、

最適:O(n)がソートされている場合、

Bubbleソートでは,最悪の場合O(n^2)の時間的複雑さがある.
各位置を探すためにはn回の巡回が必要であり,n回の回転中には要素の個数で巡回する必要があるからである.
ただし、すでにソートされている場合は、一度にソートするかどうかを知ることができます.

バブルソートの利点

in placeアルゴリズム、メモリ節約の利点
👉🏻 in placeは、追加のメモリ領域を必要とせずに、データを格納する空間内でソートされることを示す.

実装が容易な利点.ソートされたデータを巡回する場合は、n回だけ巡回できるため、ソートされたかどうかをテストするために使用できます.

泡の位置合わせの欠点

泡の並べ替えの最大の欠点はデータが多ければ多いほど性能が悪くなることである

.

最悪の場合、時間の複雑さはO(n^2)に低下し、6つのデータしかない場合は36回のスキャンが必要ですが、データが1000、10000個であれば...

function bubbleSorting(arr) {
  for (let i = 0; i < arr.length; i++) {
    let swap;
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        swap = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = swap;
      }
    }
    console.log(`${i}회전: ${arr}`);
    if (!swap){
      break;
    }
  }
  return arr;
}

console.log(bubbleSorting([4, 2, 1, 5, 3]));

i 0からarr.lengthまでドア

を回動.

内で、jはarr.length-1-iより小さいまでドアを回転する
👉🏻 arr.length - 1 - i arr[j]とarr[j+1]を比較するために使用される

配列を含まない最後のデータも検索対象に含まれるため、最後のデータ

を削除する必要がある.

2 2 2回目の回転が終了するごとに、最後のデータのソートが終了するので、i

を外す必要がある.

2swapという変数を作成し、arr[j]とarr[j+1]を比較します.
より大きいシフト可能

要素の各回転を完了し、arr[j]変数が未定義の場合は「整列完了」を表し、for文

を終了する.