7
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

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

Posted at

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でモジュールを作って確認してみます。

バブルソート

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;

クイックソート

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;

マージソート

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()とか使うといい)

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として計測してみます。

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');

実行結果

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:データ構造とアルゴリズム

「Wiki Pedia」クイックソート

「Wiki Pedia」マージソート

7
4
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
7
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?