Core > ソートと探索

ソート バブルソート クイックソート 探索 二分木探索(バイナリサーチ)

by s_hiroshi

JavaScript

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


// ソート(sort)してからサーチ(search)

// ■ ソート
// 値を並べる
//    昇順 1, 2, 3, 4, 5, ... , 100
//    降順 100, 99, 98, 97, ... , 3, 2, 1
// ● バブルソート
// ● クイックソート


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




// ● バブル(bubble)ソート
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);



// ● クイック(quick)ソート
// 参考 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)...