アルゴリズムって何だ

私はさんさです。

アルゴリズムとはよくいわれるものの、それって実際どんなものだ

そんな勉強会を先日開きました。

アルゴリズムとは

Al Khwarizmiというイラクらへんの人が由来。
彼は科学者であり、数学、天文学などの多くの分野において業績を残したそうだ。

ちなみに「アル」はアラビア語の定冠詞である。アラビア語由来の単語に「アル」で始まる物が多いのはそのため。他にも

• アルデバラン (Aldebaran)
• アルタイル (Altair)
• アルカイダ (Al Qaeda)
• アルジャジーラ (Al Jazeera)
• アルコール (Alcohol) 英語発音はアルコホールである、注意しよう

現在の用法

もっぱらコンピュータ業界で念仏のように唱えられるアルゴリズムだが、辞書によると

1. もとは算用数字を用いた筆算のこと
2. 計算や問題を解決するための手順、方式。特にコンピューターのプログラムに適用可能な手続き

出典 三省堂 大辞林

コンピュータでは適切な解を得るための手順を意味することが多い。
数学でもユークリッドの互除法や、エラトステネスの篩(ふるい)なんかは聞いたことがあったとしたら、それもアルゴリズム

よいアルゴリズムとわるいアルゴリズム

一般的によいアルゴリズムと呼ばれるのは以下の条件を満たしていることが多い。いや、満たしているべきだ。

• 意図する結果が得られること
• 計算時間、計算量が少なくすむこと
• 同じ作業の繰り返しでできること
• 使い方が限定されないこと

とりわけ重視されるのが計算時間、計算量が少なくすむことであり、この指標としてO記法なんてものが使われる。

O記法(オーダー記法)

ランダウの記号なんて別名があったりするが、ドヤ顔でいっても何もならない。実行されるアルゴリズムが、どれほどの時間、記憶領域を使用するかを評価するものである。
よく見るのは

• O(1)
• O(n)
• O(n²)
• O(n * log₂n)

Oってどうやって求めるの

難しい話はさておき、このオーダーってどうやって求めるの？という話、なんと以下のようにするだけでできるのである。

1. 計算量を示す式の最大次数に着目する
2. 最大次数の係数を無視する
3. Oとカッコをつけてやる

例：(1/6)(2n³ + 3n² + n)という計算量があったとする
ちなみに自然数の二乗の値のnまでの和の式である。

1. (1/6)(2n³) ... 最大次数以外はいらない
2. n³ ... 係数はいらない
3. O(n³)

最大次数などという呼び方をしたが、実際には計算量の中で一番増加の割合が大きなものを示したものともいえる。

ソート

アルゴリズムの例として挙げられるものといえばソートそれだけ種類が多く、計算量にも違いがあるからだ。
ここでは以下のソートについて、計算量やアルゴリズムを交えて説明する。

• バブルソート
• マージソート
• クイックソート
• ボゴソート

バブルソート

隣接交換法なんて名前がある。 一般人にトランプを渡して番号通りになるようにソートして、というとたいていこれか選択ソートをする、というぐらい誰でも思いつきそうな一般的なソート。

• 平均計算時間はO(n²)
• 安定ソート

安定ソートが何かわからないあなたはwikipedia。 アルゴリズムは単純明快である。

1. n番目の要素が、n + 1番目より大きければいれかえる
2. 1.を最初から最後まで行う
3. 2.を要素の数だけくりかえす

コードにするとこんな感じ

var bubbleSort = function(numbers) {
    var i = 0;
    var j = 0;
    var length = numbers.length;
    var temp = 0;

    for(i = 0; i < length - 1; i++) {
        for(j = 0; j < length - i - 1; j++) {
            if(numbers[j] > numbers[j + 1]) {
                swap(numbers, j, j + 1);
            }
        }
    }
};

隣り合う要素の交換が行われるため、隣接交換法と呼ばれたり、大きな数字が右側に移動していくさまが泡のようだからバブルソートなんて呼ばれているわけである。

マージソート

要素を分割、統合しながらソートする。安定した早さでソートできる。

• 平均計算時間はO(nlog₂n)
• 分割、統合のしかた次第で安定ソートになる
• javaのソートはこれを使用している

アルゴリズム

1. 要素をn分割する(一般的にはn = 2)
2. 1. を繰り返し、分割できなくなるまで分割する
3. それらをマージする。マージの際にソートする

ただし、このソートには弱点があり、一時的に配列を別の場所に記憶しなければならない。
速度はそこそこである一方、記憶領域は消費するソートといえる。

var mergeSort = function(numbers) {
    var sort = function(start, end) {
        var i = 0;
        var j = 0;
        var k = 0;
        var temp = [];

        if(start >= end) {
            return;
        }

        var mid = Math.floor((start + end) / 2);
        sort(Math.floor(start), mid);
        sort(mid + 1, Math.floor(end));
        for(i = start; i <= mid; i++) {
            temp[i] = numbers[i];
        }
        for(i = mid + 1, j = end; i <= end; i++, j--) {
            temp[i] = numbers[j];
        }
        i = start;
        j = end;
        for(k = start; k <= end; k++) {
            if(temp[i] <= temp[j]) {
                numbers[k] = temp[i];
                i++;
            }
            else {
                numbers[k] = temp[j];
                j--;
            }
        }
    };
    sort(0, numbers.length - 1);
};

クイックソート

その名の通り早いソート、ただし弱点があり、遅くなるとバブルソートと大して変わらない。

• 平均計算時間はO(nlog₂n)
• 安定ソート*ではない*

アルゴリズム

1. 要素の中から基準値を決める(ピボット、要素数/2番目の値が選ばれることが多い)
2. 基準値より左側に小さい値を、大きい値を右側に入れ替えるように移動する
3. 1., 2.を再帰的に繰り返す

このアルゴリズムの説明よりも、コードを見た方が早いと思う。

var quickSort = function(numbers) {
    var sort = function(start, end) {
        var pivot = numbers[Math.floor((start + end) / 2)];
        var i = start;
        var j = end;

        while(true) {
            while(numbers[i] < pivot) {
                i++;
            }
            while(pivot < numbers[j]) {
                j--;
            }
            if(i >= j) {
                break;
            }
            swap(numbers, i, j);
            i++;
            j--;
        }
        if(start < i - 1) {
            sort(start, i - 1);
        }
        if(j + 1 < end) {
            sort(j + 1,end);
        }
    };

    sort(0, numbers.length - 1);
};

ボゴソート

とにかく遅くてダメなソート。バブルソート以下。
一般人にトランプを渡して番号通りになるようにソートして、といっても誰もやったことがないほどのソート。

• 平均計算時間はO(n * n!)
• 安定ソートではない

アルゴリズム

1. 要素をシャッフルする
2. 要素がソートされていたら終了、されていない場合は1. をくりかえす

ソートしろといっているのにいきなりシャッフルするのがこのソートのすばらしいところである。

var bogoSort = function(numbers) {
    var shuffle = function(array) {
        var i = 0;
        var length = array.length;

        for(i = 0; i < length; i++) {
            var pos = Math.floor(Math.random() * (array.length - i)  + i);
            swap(array, i, pos);
        }
    };

    var isAscending = function(array) {
        var i = 0;
        var length = array.length;

        for(i = 0; i < length - 1; i++) {
            if(array[i] > array[i + 1]) {
                return false;
            }
        }
        return true;
    };
    var sort = function() {
        while(true) {
            if(isAscending(numbers)) {
                return;
            }
            shuffle(numbers);
        }
    }

    sort();
};

グラフで見る

計算量をグラフで比較するとこんな感じである。

縦軸がy, 横軸がxとなってしまっているが、件数xが増えるとどのぐらい計算量の目安が増えるかというのがよくわかる。
特にボゴソート(赤線)、君は真っ先に天を目指しすぎだ。

ソートをグラフィカルに見る

Jsdo.itにヨサゲなソートをしてくれるものがあったので紹介。
http://jsdo.it/norahiko/oxIy/fullscreen
ボゴソートのクソっぷりを満喫してほしい。

今回はここまで