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