会社でアルゴリズムの本を借りたのですが、ただ読んでいるだけだと、実装の時に頭から引っ張ってこれない。なので、コードを書きながら覚えていきたいと思います😄

参考にしたいコードを探すためにネットサーフィンしてみたらありました、The Algorism。格好いい？イケてる。声に出したいThe Algorism。

今日はsortを見てみようと思います。中でもbubble sort。

bubble sort

バブルソートは意外とシンプルで、配列の頭から探索して、隣り合う数で、keyが低い方の数が高い方の数より高かった場合、位置を入れ替えることです。

頭からお尻まで一つづつ数を確認していく様が、底から地上に向かって泡が上昇していく様に似ているから、バブルソートって言うらしいです。

コードを見てみます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

const bubbleSort = (arr: number[]): number[] => {
  
  for (let i = 0; i < arr.length; i++) { 
    for (let j = 0; j < arr.length-1; j++) {
      if (arr[j] > arr[j+1]) {
        let temp: number = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      }
    }
  }
  return arr;
};

下の部分で位置を交換しているようです。

1
2

  arr[j] = arr[j+1];
  arr[j+1] = temp;

ただ、バブルソートの計算時間複雑度は最悪の場合でも最良の場合でもO(n^2)なので、大きなデータセットに対してはかなり非効率。そのため実際の現場ではクイックソート、マージソート、ヒープソート等、他のソートアルゴリズムが使われ低マス

参考

ChatGPT model=gpt-4
https://github.com/TheAlgorithms/TypeScript/blob/master/sorts/bubble_sort.ts