バブルソート、クイックソート、リニアサーチ、バイナリサーチ : JavaScript

Tweet

Pocket

基本的なアルゴリズム(バブルソート、クイックソート、リニアサーチ、バイナリサーチ)をJavaScriptで書いてみる。

// 基本的なソートとサーチのアルゴリズム
// ソート
//    ● バブルソート bubble sort
//    ● クイックソート quick sort
// サーチ
//    ● リニアサーチ(線型探索) linear search
//    ● バイナリサーチ(2分探索) binary search



// ■ ソート
// 値を並べる
// ● バブルソート
// ● クイックソート


// ■ サーチ
// 値を対象の数列から探す
// ● 線形サーチ すべてを調べる O(n)
// ● バイナリサーチ O(logn)



// ● バブルソート
function bubble(arr) {
    var temp;
    for (var j = 0; j < arr.length; j++) {
        for (var i = 0; i < arr.length; i++) {
            if (arr[i] > arr[i + 1]) {
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
    }
    return arr;
}
var res = bubble([6, 2, 4, 7, 5, 1, 3, 8, 9, 0]);
console.log(res);

// ● クイックソート
// 参考 http://www1.cts.ne.jp/~clab/hsample/Sort/Sort9.html
function quicksort(arr, left, right) {
    var i = left; // 最小の添え字
    var j = right; // 最大の添え字
    var pivot = arr[Math.floor((left + right) / 2)]; // ピポッドは中央値の値
    var temp;

    while (true) {

        while (arr[i] < pivot) {
            i++;
        }
        while (pivot < arr[j]) {
            j--;
        }
        if (i >= j) {
            break; // ループを抜ける
        }
        temp = arr[i];
        arr.splice(i, 1, arr[j]);
        arr.splice(j, 1, temp);
        i++;
        j--;
    }
    if (left < i - 1) {
        quicksort(arr, left, i - 1);
    }
    if (j + 1 <  right) {
        quicksort(arr, j + 1, right);
    }

    return arr;
}
var res = quicksort([6, 2, 4, 7, 5, 1, 3, 8, 9, 0], 0, 9);
console.log(res);

// ● リニアーサーチ
function linearsearch(arr, target) {
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return 'T';
        }
    }
    return 'F';
}
console.log(linearsearch([1, 3, 5, 7, 9], 10));

// ● バイナリサーチ
function binarysearch(arr, target) {
    var a = 0;
    var b = arr.length - 1;
    while (a <= b) {
        var k = Math.floor((a + b) / 2);
        if (arr[k] == target) {
            return 'T';
        } else if (arr[k] < target) {
            a = k + 1;
        } else {
            b = k - 1;
        }
    }
    return 'F';
}
console.log(binarysearch([1, 3, 5, 7, 9], 5));

// 配列[1, 3, 5, 7, 9] のなかに10はあるか。
// a = 0;
// b = 4
// k = Math.floor((0 + 4) / 2) = Math.floor(2) = 2
// arr[k] = 5
// 5 < 10
// a = k + 1 = 3;
// b = 4
// k = Math.floor((3 + 4)) / 2 = Math.floor(3.5) = 3
// arr[k] = 7
// 7 < 10
// a = k + 1 = 4
// b = 4
// k = Math.floor((4 + 4) / 2) = Math.floor(4) = 4
// arr[k] = 9
// 9 < 10
// a =  k + 1 = 5