JavaScriptで学ぶアルゴリズム③［ソートアルゴリズム⑴］-バブルソート, 選択ソート,挿入ソート

外資系企業でソフトウェアエンジニアをしております、タロイモと言います。今日もよろしくお願いします。

前々回から、O(n)とO(1)、O(log n)アルゴリズムの紹介をしてきました。

今回はソートアルゴリズムについて紹介いたします。

1. ソートとは

ソートとは、与えられたデータ（数字）を小さい順に並べ替えることです。

日本語に直すと「整列」という言葉で表すことができます。

2. O(n^2)

O(n^2)はデータ量nが多いほど、処理が指数関数(y = x^2)のように増えていきます。

そのため、O(n^2)アルゴリズムを使う際には、データ数に応じて膨大な処理量になることがあるため要注意です。

できるならば、O(n), O(log n), O(1)アルゴリズムの関数を使うべきです。

バブルソート

右から左に向かって、隣り合っている数字を比較し、小さい順に入れ替えていくのが「バブルソート」です。

画像で表すとこんな感じになります。

①バラバラに並んだ数字データを右から比較し、
2と5は小さい順なのでそのままでOK

②6と2は小さい順ではないので、、

入れ替えます。

③7と2も小さい順でないので、、

交換し、その後の数字も順々に入れ替えていきます。

④これで2が1の右に来たので、1,2をソート済みとします。
次にまた右から5と6を小さい順に比較し、、みたいな感じで
1,2,3,4,5,6,7,8と言う順番になるように繰り返します。

バブルソートをJavaScriptで表すと以下のようになります。

let array = [1, 4, 3, 8, 7, 6, 2, 5];

function bubble_sort(array) {
 //配列の数だけループする
 for (let i = 0; i < array.length; i++) {
   //配列の左側から比較していく
   for (let j = array.length; i < j; j--) {
     //右側の数より左側の数が大きい場合は入れ替える。
     if (array[j] < array[j - 1]) {
       let tmp = array[j - 1];
       array[j - 1] = array[j];
       array[j] = tmp;
     }
   }
 }
}

bubble_sort(array);

console.log(array); // [1, 2, 3, 4, 5, 6, 7, 8]

ただJavaScriptにはsort関数が用意されているので、わざわざ使う必要がありません。

sort関数では返り値がプラスのとき（aがbより大きいとき）、aをbの後ろに並べ替えます。
反対に返り値がマイナスのとき（bがaより大きいとき）、aをbの前に並べ替えます。

let array = [1, 4, 3, 8, 7, 6, 2, 5];

array.sort(
 function(a, b) {
   return a - b;
 }
);

console.log(array); // [1, 2, 3, 4, 5, 6, 7, 8]

選択ソート

あるデータの中で線形探索で最小値を見つけ、その最小値を一番左の数字と入れ替えることを繰り返すのが「選択ソート」です。

画像で表すとこんな感じになります。

①バラバラに並んだ数字データを線形探索で、最小値を探します。
今回は1が最小値になります。

②最小値1を一番左にある3と交換します。
これで1はソート済みとなります。

③次もまた、線形探索で最小値を探します。
ソート済みの1は除外して線形探索します。
今回は2が最小値となります。

④2と一番左にある4を交換します。

⑤2がソートされたら、同様に繰り返します。今回は最小値3が一番左にあるので交換しません。
このように、最小値と一番左にある数字を交換し、
1,2,3,4,5,6,7,8の順番になるまで繰り返します。

選択ソートをJavaScriptで表すと以下のようになります。

let array = [1, 4, 3, 8, 7, 6, 2, 5];

function selection_sort(array) {
 //配列の数だけループする
 for (let i = 0; i < array.length; i++) {
   //最小値を一番右の値と仮定
   let min = array[i];
   //最小値の配列の添字も保存
   let k = i;
   //配列の隣の位置から最後まで最小値との比較を繰り返す。
   for (let j = i + 1; j < array.length; j++) {
     //最小値の方が大きかったら、その値が最小値になる。
     if (min > array[j]) {
       min = array[j];
       //最小値のある添字も更新
       k = j;
     }
   }
   //現段階の最小値を仮保存
   let tmp = array[i];
   //実際の最小値を一番左へ
   array[i] = array[k];
   //現段階の最小値を交換
   array[k] = tmp;
 }
}

selection_sort(array);

console.log(array); // [1, 2, 3, 4, 5, 6, 7, 8]

挿入ソート

データの左側から順番にソートしていくのが「挿入ソート」です。

左側の値をソート済みにし、残りのソートしていない一番左の値とソート済みの値比べ、小さい順になるように、適切な場所に挿入します。

画像で表すとこんな感じになります。

①バラバラな順番で並んでいるデータがあるとして、
一番左の7をソート済みとします。

②7をソート済みにしたら、次にソートしていない一番左の値2と7を比較します。

2は7より小さいので、7の左側に置きます。
これで2つの数がソート済みになりました。

③同様に、ソート済みのデータとソートしていない一番左の値1を比較します。

1は一番小さいので、一番左に配置します。
これを全てのデータが小さい順（1,2,3,4,5,6,7,8）になるまで繰り返して、ソートしていきます。

挿入ソートをJavaScriptで表すと以下のようになります。

let array = [1, 4, 3, 8, 7, 6, 2, 5];

function insertion_sort(array) {
 for (let i = 1; i < array.length; i++) {
   let j;
   //挿入する値をいったん変数に保存
   let tmp = array[i];
   //整列ずみのどの部分に挿入するか、整列済みの分だけ整列済みの大きい方から順にループ
   for (j = i - 1; j >= 0; j--) {
     //挿入する変数tmpが、整列済みの変数array[j]より大きい場合、そのままループから抜け出すbreak
     if (tmp > array[j]) {
       break;
     } else {
       //挿入する変数tmpが整列済みの変数array[j]より小さい場合、array[j]の添字が一個増えたところにarray[j]の値を保存。
       array[j + 1] = array[j];
     }
   }
   //breakした場合、挿入する値はarray[j+1]に
   array[j + 1] = tmp;
 }
}

insertion_sort(array);​

console.log(array); // [1, 2, 3, 4, 5, 6, 7, 8]​

お疲れ様でした。

次回は、マージソートについて解説していこうと思います。

今回もご精読ありがとうございました。