【アルゴリズム(JS実装)】Bubble Sort
どうも!わくばです!
今日から1日1アルゴリズムずつ記事にしていこうかなと思います。
今までなんとなく避けてきたんですがそろそろそうも行かなくなってきたので、、、
普段codewarsというサイトでコーディングの勉強をしているんですが、上級になると結構難しくなるんですよね。codewarsではレベルのことをkyuといって、そのkyuが上がってくるとどうにも素人の発想では回答できない問題も増えてきます。kyuが上がるのに比例して1問にかかる時間が長くなってきまして、そろそろ真面目にアルゴリズムを勉強しておかないと、この先いくら時間があってもてりないのでは、、、というわけです(笑)
勉強の手順としては
- VisuAlgoというサイトから適当にアルゴリズムを一つ選ぶ。
- JavaScriptで実装していみる
といった感じです。
JavaScriptを選んだ理由は、Visualgoのソースコードが載っていなくて、一番馴染みがある言語だからです。
・Bubble Sort
今日勉強したのはBubble Sortです。仕組みは簡単で、「隣接する二項を比較して条件に応じて入れ替える」操作を左から右へ繰り返し行うものです。
「バブル」と呼ばれる所以は、要素がループ処理で徐々に適切な場所に移動し且つばらばらに終了していく感じが、水の底から泡が発生して無秩序に弾ける様子に似ているからだそうです。
今回は配列の要素を昇順に並べ替えるというアルゴリズムを実装してみました。
const bubbleSort = arr => { //分割代入でArrayオブジェクトからlengthを独立させる(必須ではない) const { length } = arr; //swappedがtrueの間だけwhileループを実行 let swapped = false; do { swapped = false; for (let j = 0; j < length - 1; j++) { if ( arr[j]> arr[j+1] ) { //スワップ処理 [ arr[j], arr[j+1] ]=[ arr[j+1], arr[j] ] swapped = true; } } }while(swapped); return arr; }
ループ処理を二重にするというシンプルなアルゴリズムです。Big O notationで計算すると\(O(n)\)が二重なので\(O(n^2)\)の処理になります。
whileではなくforで配列の要素ぶんループする実装もありましたが、whileの方が必要最低限の処理で済むのでスッキリです。
次回はなににしようか。個人的にグラフ理論が楽しみです(笑)
では。