@blog.justoneplanet.info

日々勉強

JavaScriptでマージソート

■実装

var n = 10;
var a = [];
for(var i = 0; i < n; i++){
    a[i] = Math.round(Math.random() * n);
}
array = a.concat();


/**
 * msort
 * @param {Object} ary
 */
var msort = function(ary){
    if(ary.length < 2){
        return ary;
    }
    else{
        var l = msort(ary.splice(0, ary.length >>> 1));// 配列の左半分
        var r = msort(ary.splice(0));// 残りの部分配列
        console.log(l.toString());
        console.log(r.toString());
        // 以下の部分でマージする
        while(!(l.length < 1 && r.length < 1)){
            if(!l[0]){
                ary.push(r.shift());
            }
            else if(!r[0]){
                ary.push(l.shift());
            }
            else if(l[0] < r[0]){// 小さい方をpush
                ary.push(l.shift());
            }
            else{
                ary.push(r.shift());
            }
        }
        console.log(ary.toString());
        console.log('===============');
        return ary.concat(l, r);
    }
}


msort(a);
console.log("before : " + array.toString());
console.log("after  : " + a.toString());

■特性

  • 最悪時の計算量はO(n log n)
  • 安定ソート
  • 平均時性能はO(n log n)

JavaScriptでバケツソート

■実装

var a = [5, 7, 3, 9, 1, 4, 6, 8, 2, 0];
array = a.concat();


/**
 * bucketSort
 * @param {array} ary
 */
var bucketSort = function(ary){
    var hash = function(value){
        return Math.floor(value / 3);
    }// hash関数
    
    var bucket = [];
    for(var i = 0; i < ary.length; i++){
        if(!bucket[hash(ary[i])]){
            bucket[hash(ary[i])] = [ary[i]];
        }
        else{
            bucket[hash(ary[i])].push(ary[i]);
        }
    }// bucket配列に格納(各bucketは配列となっている)
    console.log(JSON.stringify(bucket));
    
    // 衝突したbucket内で挿入ソート
    for(var i = 0; i < bucket.length; i++){
        for(var i2 = 1; i2 < bucket[i].length; i2++){
            var value = bucket[i][i2];
            for(var i3 = i2 - 1; i3 >= 0; i3--){
                if(value <= bucket[i][i3]){
                    bucket[i][i3 + 1] = bucket[i][i3];
                }
                else{
                    break;
                }
            }
            bucket[i][i3 + 1] = value;
        }
    }
    console.log(JSON.stringify(bucket));
    
    // bucketの先頭の要素から取り出し、元の配列を上書きする
    var store = 0;
    for(var i = 0; i < bucket.length; i++){
        if(bucket[i]){
            for(var i2 = 0; i2 < bucket[i].length; i2++){
                ary[store++] = bucket[i][i2];
            }
        }
    }
}


bucketSort(a);
console.log("before : " + array.toString());
console.log("after  : " + a.toString());
// ハッシュ関数と要素の分布によって衝突することもある
// 以下がハッシュ関数に対して理想的な分布だった場合
// var a = [15, 21, 9, 27, 3, 12, 18, 24, 6, 0];
// [[0],[3],[6],[9],[12],[15],[18],[21],[24],[27]]
// 以下が衝突が起こった場合
// var a = [5, 7, 3, 9, 1, 4, 6, 8, 2, 0];
// [[0,1,2],[3,4,5],[6,7,8],[9]]
// 衝突が起こると挿入ソートの回数が増えて性能が低下する

■特性

  • 高速ハッシュ関数を使って、要素が一様に分割できる必要がある

JavaScriptで数え上げソート

データが取り得る値の範囲が分かっている場合、O(n log n)の限界を超えて、O(n)の計算量でソートできる。

■実装

var a = [5, 7, 3, 9, 1, 4, 6, 8, 2, 0];
array = a.concat();


/**
 * countingSort
 * @param {array} ary
 * @param {int} max
 */
var countingSort = function(ary, max){
    var bucket = [];
    for(var i = 0; i <= max; i++){
        bucket.push(0);
    }// バケツの準備
    for(var i = 0; i < ary.length; i++){
        bucket[ary[i]]++;
    }// i番目の要素に与えられた配列の要素値iの出現回数が記録される
    
    var store = 0;
    for(var i = 0; i <= max; i++){
        while(bucket[i]-- > 0){
            ary[store++] = i;
        }
    }// 出現回数に応じて元の配列を上書きする
}


countingSort(a, 9);
console.log("before : " + array.toString());
console.log("after  : " + a.toString());
//before : 5,7,3,9,1,4,6,8,2,0
//after  : 0,1,2,3,4,5,6,7,8,9

■特性

  • 要素の値に重複があっても良い
  • 要素の値が取り得る最大値が分からなくてはならない
  • 計算量はO(n)である

JavaScriptでヒープソート

■実装

var n = 10;
var a = [];
for(var i = 0; i < n; i++){
    a[i] = Math.round(Math.random() * n);
}
array = a.concat();


/**
 * swap
 * @param {array} ary
 * @param {int} x
 * @param {int} y
 */
var swap = function(ary, x, y){
    console.log(ary.toString());
    var a = ary[x];
    var b = ary[y];
    ary[x] = b;
    ary[y] = a;
    console.log(ary.toString());
    console.log('---');
    return true;
}

/**
 * heapify
 * 3要素を比較し最も大きい要素を親とする
 * @param {array} ary
 * @param {int} i
 * @param {max} max
 */
var heapify = function(ary, i, max){
    var l = 2 * i + 1;
    var r = 2 * i + 2;
    var li = 0;
    if(l < max && ary[l] > ary[i]){
        li = l;
    }
    else{
        li = i;
    }
    if(r < max && ary[r] > ary[li]){
        li = r;
    }
    if(li !== i){
        swap(ary, i, li);// 比較した3要素の最大値を親に移動…(a)
        heapify(ary, li, max);
        /*(a)によりiの子孫(孫以下)のノードでヒープが崩れた可能性がある*/
        /*従って、aryのヒープ特性を保持するため、leaf方向に向けて再帰でheapify*/
    }
}

/**
 * buildHeap
 * 子を持つ要素のうち最も大きいインデックスを持つ要素より前をheapifyする
 * @param {array} ary
 */
var buildHeap = function(ary){
    for(var i = Math.floor(ary.length / 2) - 1; i >= 0; i--){
        heapify(ary, i, n);
    }
}

/**
 * hsort
 * @param {array} ary
 */
var hsort = function(ary){
    buildHeap(ary);// 初期のヒープ構造を生成
    for(var i = ary.length - 1; i > 0; i--){
        swap(ary, 0, i);// 先頭の最大値と最後尾の要素をswap
        heapify(ary, 0, i);// 最後尾の要素を除いてヒープ構造を再構築
    }
}


hsort(a);
console.log("before : " + array.toString());
console.log("after  : " + a.toString());

■特性

  • データの出現順序による計算量の変化が小さく、計算量はO(n log n)となる
  • 要素を頻繁に入れ替える
  • 安定整列ではない

JavaScriptでクイックソート

■実装

var n = 10;
var a = [];
for(var i = 0; i < n; i++){
    a[i] = Math.round(Math.random() * n);
}
array = a.concat();


/**
 * qsort
 * 配列の左端と右端を指定してソートし分割位置を返す
 * @param {array} ary
 * @param {int} l
 * @param {int} r
 */
var qsort = function(ary, l, r){
    var pi = partition(ary, l, r);// 分割位置
    if(l < r){
        qsort(ary, l, pi - 1);// 左半分のqsort
        qsort(ary, pi + 1, r);// 右半分のqsort
    }
}

/**
 * swap
 * 配列の要素を指定のインデックスで入れ替える
 * @param {array} ary
 * @param {int} x
 * @param {int} y
 */
var swap = function(ary, x, y){
    console.log(ary.toString());
    var a = ary[x];
    var b = ary[y];
    ary[x] = b;
    ary[y] = a;
    console.log(ary.toString());
    console.log('---');
    return true;
}

/**
 * partition
 * 
 * @param {array} ary
 * @param {int} l
 * @param {int} r
 */
var partition = function(ary, l, r){
    var index = l + Math.floor(Math.random() * (r - l + 1));// lからrの範囲でランダム位置
    swap(ary, index, r);// 右端に軸値を移動
    //================================================
    // 以下の部分において軸値以下の数値を左から詰めていく
    var store = l;//置き場所
    for(var i = l; i < r; i++){
        if(ary[i] <= ary[r]){
            if(swap(ary, i, store)){
                store++;
            }
        }
    }
    //================================================
    swap(ary, store, r);// 軸値を軸値以下が並んでる列のすぐ右側に配置
    return store;
}


qsort(a, 0, a.length - 1);
console.log("before : " + array.toString());
console.log("after  : " + a.toString());

■特性

  • 常に軸値が最小値か最大値だった場合にO(n ^ 2)の計算量となる
  • 平均時性能はO(n log n)である

JavaScriptで挿入ソート

挿入ソートとは、配列Aのx番目の追加要素aをxから先頭に向かって比較し、挿入位置を特定する方法。

■実装

var n = 10;
var a = [];
for(var i = 0; i < n; i++){
    a[i] = Math.round(Math.random() * n);
}
console.log(a);
ary = a.concat();

// sort
for(var i = 1; i < ary.length; i++){
    var val = ary[i];
    for(var i2 = i - 1; i2 >= 0; i2--){
        if(ary[i2] > val){
            ary[i2 + 1] = ary[i2];
        }
        else{
            break;
        }
    }
    ary[i2 + 1] = val;
}

console.log(ary);

■特性

  • 最初から集団がほぼ整列しているような場合に適している
  • ランダムなデータに対しては効率が悪い
  • 計算量が最小となるのは集団が完全に整列していた場合でO(n)である
  • 計算量が最大となるのは集団が完全に逆順だった場合でO(n ^ 2)である
  • 平均時性能はO(n ^ 2)である。