ソートアルゴリズムの計算量について、復習してみた

GWいかがお過ごしでしょうか。
私は転職して、本格的に開発側へシフトしたこともあって
いろいろなアルゴリズムに触れる機会が増えています。
また、JS系のライブラリやフレームワークを業務で使う事が多いので
今回は計算量を題にして、JavaScriptのプログラミングにも触れながらまとめてみようと思います。

## 計算量って？
情報科学の処理量を表し、アルゴリズムの処理時間を比較するために用いられます。
計算量は、オーダー記法を用いて表現します。

例えば処理するデータ数をnとしたとき、**O(1)**や**O(n)**といった書き方をします。
**O(1)**といった表記は、定数オーダーともいい、データ量に寄らずに処理時間が一定であることを表しています。
**O(n)**は、処理時間がデータn個に比例することを表しています。

また、例えば処理時間がデータn個の2倍かかるとした場合、計算量を**O(2n)**と書きたくなりますが
この定数2は無視をして**O(n)**と書きます。

#### どう使われる？
O(1)とO(n)では、データ量が増えるとO(1)のほうが早そうですよね。
計算量を出すことで、処理時間を予測することは、アルゴリズムやデータ構造の選定に役立つわけです。

## ソートアルゴリズムの計算量
今回は代表的なソートのアルゴリズムの計算量を見ていきます。

#### バブルソート

配列の要素の前から順番に比較してソートをします。
計算量は、**O(n^2)**になります。

#### クイックソート

基準値（ピボット）を決めてそれよりも大きい値小さい値を集めます。
この処理を再帰的に行ってソートをします。
計算量は、ピボットの選び方によって異なりますが、平均すると**O(nlogn)**になります。
（最悪計算量は**O(n^2)**)

#### マージソート

配列を最小単位まで分割し、それぞれをマージしながらソートをする。
計算量は**O(nlogn)**になります。

### 計算量（処理時間）を確かめてみる

せっかくなので、今学習中のJavaScriptでモジュールを作って確認してみます。

#### バブルソート
```javascript:bublesort.js
'use strict';
// バブルソート
function bubbleSort(array) {
  let result = Array.from(array);
  for(let e = result.length - 1; e > 0; e--){
    for(let i = 0; i < e; i++){
      if(result[i] > result[i + 1]){
        [result[i], result[i+1]] = [result[i+1], result[i]];
      }
    }
  }
  return result;
}

module.exports = bubbleSort;
```

#### クイックソート

```javascript:quicksort.js
'use strict';

function quickSort(array, start = 0, end = array.length - 1){
// クイックソート
  if(end <= start){
    return;
  }

  const pivot = selectPivot(array, start, end);

  let left  = start;
  let right = end;
  while(true){
    while(array[left]  < pivot) { left++; }
    while(array[right] > pivot) { right--; }
    if(left >= right) { break; } // leftとrightが逆転 = 探索終了
    [array[left], array[right]] = [array[right], array[left]];
    left++;
    right--;
  }

  // 前半後半で、再起処理
  quickSort(array, start, left - 1);
  quickSort(array, right + 1, end);

    // ピボットを選ぶ
  function selectPivot(array, start , end){
    // 配列の先頭、中央、末尾の中央値をピボットとする。
    const [x, y, z]  = [ array[start],
                         array[Math.floor((start + end) / 2.0)],
                         array[end] ];
    if(x > y){
      return y < z ? y :
             z < x ? x : z;
    } else {
      return z < y ? y :
             x < z ? x : z;
    }
  }
}

module.exports = quickSort;

```

#### マージソート

```javascript:margesort.js
'use strict';
// マージソート
function margeSort(array){
  if( array.length < 2 ){ return array; }
  const middle = Math.floor(array.length / 2.0);
  let left  = array.slice(0, middle);
  let right = array.slice(middle);

  return marge(margeSort(left), margeSort(right));

  // 配列をソートしながら一つに統合する
  function marge(left, right){
    let result = [];
    let leftIndex  = 0;
    let rightIndex = 0;

    while(leftIndex < left.length && rightIndex < right.length){
      if(left[leftIndex] < right[rightIndex]){
        result.push(left[leftIndex++]);
      }else{
        result.push(right[rightIndex++]);
      }
    }

    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
  }
}

module.exports = margeSort;
```

#### 処理時間を計測するためのモジュール
引数で与えた関数の処理時間を計測します。
（ブラウザ上で動かすなら、console.time系ではなくてperformance.now()とか使うといい）

```javascript:measureTime
'use strict';

function measureElapseTime(func, dataNum, targetName){
  let measureTarget = `${targetName} times elapse time`;

  // ランダムな配列データを作成
  const array = [];
  for(let i = 0; i < dataNum; i++) {
    const value = Math.random();
    array.push(value);
  }
  
  console.time(measureTarget);
  func(array);
  console.timeEnd(measureTarget);
}

module.exports = measureElapseTime;
```


#### 仕様例

今回はサンプルデータを10000として計測してみます。

```javascript:execute.js
const measureElapsetime = require('./measureTime');
const bubleSort = require('./bublesort');
const quickSort = require('./quicksort');
const margeSort = require('./margesort');

const dataNum = 10000;

measureElapsetime(bubleSort, dataNum, 'BubleSort');
measureElapsetime(quickSort, dataNum, 'QuickSort');
measureElapsetime(margeSort, dataNum, 'margeSort');

```


#### 実行結果

```terminal
BubleSort times elapse time: 315.860ms
QuickSort times elapse time: 18.161ms
margeSort times elapse time: 17.550ms
```

確かに、クイックソートや、マージソートのほうがバブルソートのよりも約20倍早いことがわかります。
（もう少し早くなっても良さそうですが…）
また、クイックソートとマージソートの平均計算量が同等（**O(nlogn)**）なので、近いこともわかります。


# 終わりに
他にもヒープソートやバケットソートなど、ソートアルゴリズムはまだまだあります。
これらをソースコードにして、処理時間を確かめてみるのもいいかもしれません。


# 参考

[「Subterranean Flower Blog」 【連載記事】JavaScriptでプログラミングを学ぶ　その5：データ構造とアルゴリズム](https://sbfl.net/blog/2018/10/14/javascript-programming-5/)

[「Wiki Pedia」クイックソート](https://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88)

[「Wiki Pedia」マージソート](https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88)