バブルソート（単純交換ソート）

次の$n$個の数からなる数列を考える。 $$ a_0, a_1, \cdots, a_i, \cdots, a_{n-1} $$ この数列を次のような手順で昇順に並べ替える。

• $a_0$と$a_1$以降を一つずつ比較し、$a_0$の方が大きければ交換
• $a_1$と$a_2$以降を一つずつ比較し、$a_1$の方が大きければ交換
• （以降も繰り返し）
• $a_i$と$a_{i + 1}$以降を一つずつ比較し、$a_i$の方が大きければ交換
• （以降も繰り返し）
• $a_{n-2}$と$a_{n-1}$を比較し、$a_{n-2}$の方が大きければ交換

一般化すると、 $a_{i(0 < i < n-1)}$と$a_{j(i + 1< j < n)}$を比較・交換すればよい。

BubbleSort.js

function BubbleSort(a)
{
    var n = a.length;
    
    for (var i = 0; i < n - 1; i++) {
        
        for (var j = i + 1; j < n; j++) {
            
            if (a[i] > a[j]) {
                [a[i], a[j]] = [a[j], a[i]];
            }
        }
    }
    
    return a;
}

単純選択ソート

次の手順をすべての$i$に対して繰り返すことで、昇順に並べる。

• $a_i$が最小値だと仮定する
• $a_i$と$a_{i+1}$以降の数を比較し、$a_i < a_{i+1+?}$となるものがあれば、$a_{i+1+?}$を最小値と仮定する
• $a_{i+1+?}$と$a_{(i+1+?)+1}$以降の数を比較し、同様にして最小値を更新する
• （繰り返し）
• こうして見つかった最小値$a_{min}$を、$a_i$と交換する。

$i+1$を$j$とおくと、すっきりとまとめられる。

BubbleSort.js

function BubbleSort(a)
{
    var n = a.length;
    
    for (var i = 0; i < n - 1; i++) {
        
        for (var j = i + 1; j < n; j++) {
            
            if (a[i] > a[j]) {
                [a[i], a[j]] = [a[j], a[i]];
            }
        }
    }
    
    return a;
}

単純挿入ソート

以下の操作をすべての$i(>0)$に対して繰り返すことで、昇順に並べ替える。

• $a_i$より左にある数（$a_0$, $a_1$, ... , $a_{i-1}$）を右から一つずつ見ていき、$a_i$より小さいものがあれば、右に1個ずらしてその場所を空けておく
• 最終的に空いた場所に$a_i$を挿入する

InsertSort.js

function InsertSort(a)
{
    var n = a.length;
    
    for (var i = 1; i < n; i++) {
        
        insertPosition = i;
        
        for (var j = i - 1; j >= 0; j--) {
            
            if (a[i] < a[j]) {
                a[j + 1] = a[j];
                insertPosition--;
            }
        }
        
        a[insertPosition] = a[i];
    }
    
    return a;
}

二分探索

昇順にソートされた数列の中から、次のような絞り込みを繰り返すことで、目的の数$target$を見つけ出す。

• $target > a_{center}$なら、$a_{center}$より左に$target$があるため、前半を探索範囲から除く
• $target < a_{center}$なら、$a_{center}$より右に$target$があるため、後半を探索範囲から除く
• $target = a_{center}$なら、探索終了

BinarySearch.js

function BinarySearch(a, target)
{
    var leftmost = 0;
    var rightmost = a.length - 1;
    var center = (leftmost + rightmost) / 2;
    
    while (leftmost <= rightmost) {
        
        if (target === a[center]) {
            
            return center;
            
        } else if (target > a[center]) {
            
            leftmost = center + 1;
            
        } else if (target < a[center]) {
            
            rightmost = center - 1;
        }
    }
    
    return -1;
}