TIL 82|ソート(2)-JSによるBubble Sortの実装

6117 ワード
bubblesort JavaScript Sort テキストリンク

Bubble Sort


コンセプト


2つの隣接データ値を交換位置で並べ替えるアルゴリズム.
ソートプロセスにバブルが現れるように見えるため、このような名前が付けられています.

プロセス


  • 現在の要素が次の要素の値より大きい場合、この2つの要素は変更されます.
    • 1回の
  • 要素全体の比較が完了すると、最小(または最大)値はエッジにあり、2回目の比較では、最小(または最大)値を除く残りの要素の範囲で比較されます.
    • その結果,繰り返しが進むにつれて無視の範囲が大きくなり,速度が速くなる.

    時間の複雑さ


    Big-O : O(n^2)


    Big-Ω : Ω(n^2)

    (n-1)*(n-2) = n^2-3n+2整列するかどうかにかかわらず、ループを迂回して比較する必要があるため、実行時間の上下限は同じです.

    メリットとデメリット


    長所

  • は簡単で、ソースコードが直感的です.
  • メモリ節約O(1)
    ソートするアレイで他のメモリ領域をスワップする必要はありません
    (その場でソート)

    • 短所

  • 時間複雑度低効率

    • 特長


    Stable


    冗長データがある場合は、データを交換するのではなく、ソートが終了しても既存の冗長データの順序を維持します.

    コード#コード#

    function bubbleSort (array) {
  for(let i=0; i<array.length; i++){
    let swap;
    for(let j=0; j<array.length-1-i; j++){
      if(array[j]>array[j+1]){
        swap = array[j];
        array[j] = array[j+1];
        array[j+1] = swap;
      }
    }
    console.log(`${i}회전 : ${array}`)
    if(!swap){
      break;
    }
  }
  return array;
}
console.log(bubbleSort([5,7,3,4,1,6,2]));

    参考資料
    CS50
    https://medium.com/@peterlin5301997/bubble-sort-5a66156c942e
    https://im-developer.tistory.com/133
    BOJ-2300基地局
    イントラネットページの構築-01