アルゴリズムの中には様々な整列方法がありますよね。
その中で今回はよく聞くけど、実際に使われているのはあまり見ない「バブルソート」についてまとめてみました。
バブルソートとは？
自分の言葉で整理してみる
配列中で連続した2つの要素を比較し、交代し続けること
定義
wikipediaさんによる定義は以下のようです。
バブルソート（英: bubble sort）は、隣り合う要素の大小を比較しながら整列させるソートアルゴリズム。
バブルソートの動き
「隣り合う要素の大小を比較」を繰り返すことで整列をしています。
その過程の中で毎回「最大値を最終indexまでに持っていく」をすることになっていますね。
以下のサイトから可視化されたバブルソートのみることができたので、持ってきました。
今回用いるデータはこれ。[29, 10, 14, 37, 14]です。
イテレーション１
イテレーション２
イテレーション３
実装
まずは自分で
myBubbleSort.js
let array = [29, 10, 14, 37, 14];
let num = 1;
while (true) {
let isSwapped = false;
for (let i = 0; i < array.length - num; i++) {
if (array[i] > array[i + 1]) {
[array[i], array[i + 1]] = [array[i + 1], array[i]];
isSwapped = true;
}
}
if (!isSwapped) {
break;
}
num ++;
}
console.log(array);
通った！
工夫したところ
- モダンなJSで
- 早期終了ができるように
isSwappedを設定
先にビジュアルの挙動が見られたため、2番の工夫にたどり着くことができました。
ビジュアル化最高。
正解のコード
こちらはUdemyで受けている講義の正解例です。
概ね似ていますね。
しかし、while (true)だとソートされている配列の中は無限に回ってしまうところがクリティカル...😅
function bubbleSort(arr) {
var noSwaps;
for (var i = arr.length; i > 0; i--) {
noSwaps = true;
for (var j = 0; j < i - 1; j++) {
console.log(arr, arr[j], arr[j+1]);
if (arr[j] > arr[j+1]) {
var temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
noSwaps = false;
}
}
if (noSwaps) break;
}
return arr;
}
修正すると...
myBubbleSort.js
let array = [29, 10, 14, 37, 14];
for (let num = 1; num < array.length; num++) {
let isSwapped = false;
for (let i = 0; i < array.length - num; i++) {
if (array[i] > array[i + 1]) {
[array[i], array[i + 1]] = [array[i + 1], array[i]];
isSwapped = true;
}
}
if (!isSwapped) break;
}
console.log(array);
時間計算量
二重ループなので、O(n^2)になりそうですね。
しかし、早期終了ができる場合、ベストはO(n)になりますかね？
終わりに
書いてみて、効率のいいソートではないと感じました。
配列の中身を全部見に行くため、ある程度ソートされている場合は他のソートを使うべきですね。
参考
この記事の内容は主に以下のUdemy講義を元にしています。