[Javascript] JS Algorithm

3797 ワード
TIL JavaScript algorithm テキストリンク
JSコードTaka

バブル整列(Bubble Sort)


Question


バブルソートは隣接データを交換することによってソートするアルゴリズムである.
これはアルゴリズムのソートが泡のように見えることから命名された.
下図を見てください.
アルゴリズムはすぐに理解できるかもしれません.

以下の位置合わせがない場合はidex 0<->1から交換を開始します.
2つの隣接する数字を比較し、より大きな数字を右側に移動します.
6 5 3 2 8
-> 5 6 3 2 8
そしてindex 1<->2
5 6 3 2 8
-> 5 3 6 2 8
そしてindex 2<->3
5 3 6 2 8
-> 5 3 2 6 8
そしてindex 3<>4
5 3 2 6 8
-> 5 3 2 6 8
最後の2つの数を比較すると、最大数が最後のindexにあることがわかります.
最初からやり直す.
5 3 2 6 8
-> 3 5 2 6 8
3 5 2 6 8
-> 3 2 5 6 8
3 2 5 6 8
-> 3 2 5 6 8
今回の両替はindex 2と比較して停止すればいいです.
最後のインデックスが最大数でソートされているためです.
このように比較と置き換えを続ければいい!
  • コードカタ
    numsという名前の配列をくれれば、Bubbleソートアルゴリズムで配列をソートします.

    • My Answer

    const bubbleSort = nums => {
  for(let i=0; i<nums.length; i++){
    for(let j=0; j<nums.length-i-1; j++){
      if(nums[j] > nums[j+1]){
        let temp = nums[j];
        nums[j] = nums[j+1];
        nums[j+1] = temp;
      }
    }
  }
  return nums;
}
    21.02.16
    [TIL] Making a To Do LIST - 2