JavaScriptでアルゴリズムを学習する③

はじめに
バブルソートとは何か
JavaScriptでバブルソートを実装する
終わりに
参考

はじめに

こんにちは、インプルの山形です。今回はJavaScriptでアルゴリズムを実装するシリーズ第三弾というです！

第一弾(参照URL:https://ramble.impl.co.jp/4027/）、第二弾(参照URL:https://ramble.impl.co.jp/4079/)では選択ソート、クイックソートを実装しました。

今回はバブルソートアルゴリズムをJavaScriptを通して学習していきたいと思います！

まずはそもそもバブルソートとは何なのかみていきましょう！

バブルソートとは何か

以下の引用からまずはその定義を確認します

バブルソート（英: bubble sort）は、隣り合う要素の大小を比較しながら整列させるソートアルゴリズム。
全ての要素に関して、隣接する要素と比較し順序が逆であれば入れ替える。これを要素数-1回繰り返すことでソートを行う。なおこの繰り返しは、入れ替えが起こらなくなった時点で（それ以降は何度繰り返しても変化が起こらなくなるので）中断することができる。
引用元:Wikipwdia

具体的な例を挙げて、説明すると、例えば、[3,4,2,1.0]というは配列があったとします。この配列の中の要素を昇順に並べ替えるとします。

まず、配列内の最初の要素である「3」の並びを考えます。このソートでは「隣り合う要素の大小を比較しながら整列させるアルゴリズム」とあるので、となりの要素である「４」との比較を行います。昇順に並べ替えることを考えるとき、「３」と「４」では、「４」のほうが大きいので、この比較においては入れ替えは行われません。

次に「４」の並びを考えます。したがって隣の要素である「２」との比較を行います。昇順に並べ替えることを考えるとき、2 < ４　が成立するので、この比較においては並べ替えが発生します。この時点で、ソート対象の配列は[3,2,4,1,0]となります。次に「４」と「１」の比較を行い、ここでも交換が発生するので、[3,2,1,4,0]となり、「0」との交換も発生することも考慮すると、最終的に[3,2,1,0,4]の状態で一回目のソートが完了します。2回目の操作は「3」の比較から始まり、上記と同じ操作を繰り返すことで、最終的に[2,1,0,3,4]の状態でソート完了、3回目以降も同様の操作を行うことでソートしていきます。

注意しなければいけないこととして、1回のソートが終了するごとにソートの探索範囲、つまり、ソート対象の配列要素の範囲を1つづつ小さくしていかなければいけない、ということです。なぜなら、1回のソートが完了するごとに右端の数は整列完了とみなすことができるから、です。

どういうことかというと、上記の具体例の説明の１回目の操作を見ても分かる通り、「４」という数字は、この配列内の要素における最大数であり、この「４」が右端に来た時点で「４」はこれ以上並び替える必要がありません。「４」は整列完了と言い換えることができ、次のソートにおいては右端の要素を除いた、「3,2,1,0」の範囲で3回分の比較操作を行えば良いということです。

これを全ての操作に適用すると、1回のソートが完了するごとにソートの探索範囲が1つ小さくなっていくということもお分かりいただけると思います。

さて、ここまではバブルソートがどういったものかの説明をしてきました。次に実際にコードでどのように実装するか見ていきます。

JavaScriptでバブルソートを実装する


const bubbleSort = (array, range, index) => {

    if(range > 1){
        if(index < range){
          if(array[index] > array[index + 1]){
            [array[index + 1], array[index]] = [array[index], array[index + 1]]
          }
          bubbleSort(array, range, ++index);
        }
      bubbleSort(array, --range, 0);
    }
    return array;
}


const testCase = [9, 23, 76, 12, 3, 2];
const result = bubbleSort(testCase, testCase.length, 0);
console.log(result);  // [ 2, 3, 9, 12, 23, 76 ]

今回も再帰関数を用いての実装です。ifがネストして少々見ずらい実装になっていますが、直感的に書くとこのような感じになると思います。

解説すると、rangeは1回の探索における範囲を指しています。つまり、配列内の要素のどこまでを操作の対象にするかという範囲のことを指しています。初期値は配列の要素数です。rangeが1未満になったらソート完了で、配列を返しています。1より大きい場合に、探索範囲を縮めながら再帰関数を実行させているイメージです。

次に、bubbleSort関数の第三引数に注目してください。このindexはソートの操作をする対象配列の開始点を数値で格納しています。バブルソートは「隣り合う要素を順番に比較して交換する」アルゴリズムとありました。そのため、探索範囲内で「ある配列要素のindex番目とindex+1番目」を比較する必要があり、今どことどこを比較しているかの追跡が必要になるのです。その追跡のための変数がindexと思ってください。

上記の解説を前提に話を進め、まとめると以下のようになっています。

内側から2番目のif文が意味しているところは、比較の開始点(index) < 探索範囲(range) を満たしている時に、実行される処理であり、ここで array[index] > array[index+1]であれば、交換を行なっています。そして最後にindexを1つインクリメントして再帰関数を実行しています。(bubbleSort(array, range, index+1)の部分ですね。)indexを1づつインクリメントしていくとrangeの数に近づいていきます。

そして、比較の開始点(index) < 探索範囲(range)を満たさなくなった時、というのは、最初の説明のn表現をかりると「右端が整列済j」となった状態を意味しているので、探索範囲を1つ縮め、さらに、探索の開始点を0に初期化して、再帰関数を実行しています。(これはbubbleSort(array, range-1, 0)の処理のことですね。)

rangeを1つづデクリメントして、range < 1を満たさなくなった時、つまり、それ以上比較交換の必要がなくなった時に初めて、arrayを返却する処理となっています。