@blog.justoneplanet.info

■実装

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)である