Array.prototype.swap=function(a, b)
{
var tmp=this[a];
this[a]=this[b];
this[b]=tmp;
}
function partition(array, begin, end, pivot)
{
var piv=array[pivot];
array.swap(pivot, end-1);
var store=begin;
var ix;
for(ix=begin; ix<end-1; ++ix) {
if(array[ix]<=piv) {
array.swap(store, ix);
++store;
}
}
array.swap(end-1, store);
return store;
}
function qsort(array, begin, end)
{
if(end-1>begin) {
var pivot=begin+Math.floor(Math.random()*(end-begin));
pivot=partition(array, begin, end, pivot);
qsort(array, begin, pivot);
qsort(array, pivot+1, end);
}
}
function quick_sort(array) {
qsort(array, 0, array.length);
}
function measureSortOrg(array) {
var start = new Date();
array.sort();
var diff = new Date() - start;
return { res: array, diff: diff };
}
function measureSortCustom(array) {
var start = new Date();
quick_sort(array);
var diff = new Date() - start;
return { res: array, diff: diff };
}
var arrayOrg = [];
for (var i = 0; i < 5000; i++) {
arrayOrg.push(Math.random());
}
var arrayCustom = arrayOrg.slice(0);
var arrayOrg = arrayOrg.slice(0);
var resOrg = measureSortOrg(arrayOrg);
var resCustom = measureSortCustom(arrayCustom);
var equal = true;
for (var i = 0; i < resOrg.length; i++) {
if (Math.abs(resOrg[i] - resCustom[i]) > 0.00000001) {
equal = false;
break;
}
}
print("lengthOrg: " + resOrg.res.length + ', timeOrg: ' + resOrg.diff + 'ms\n' + "lengthCustom: " + resCustom.res.length + ', timeCustom: ' + resCustom.diff + 'ms\n' + 'equal: ' + equal);
QXJyYXkucHJvdG90eXBlLnN3YXA9ZnVuY3Rpb24oYSwgYikKewogICAgICAgIHZhciB0bXA9dGhpc1thXTsKICAgICAgICB0aGlzW2FdPXRoaXNbYl07CiAgICAgICAgdGhpc1tiXT10bXA7Cn0KICAKZnVuY3Rpb24gcGFydGl0aW9uKGFycmF5LCBiZWdpbiwgZW5kLCBwaXZvdCkKewogICAgICAgIHZhciBwaXY9YXJyYXlbcGl2b3RdOwogICAgICAgIGFycmF5LnN3YXAocGl2b3QsIGVuZC0xKTsKICAgICAgICB2YXIgc3RvcmU9YmVnaW47CiAgICAgICAgdmFyIGl4OwogICAgICAgIGZvcihpeD1iZWdpbjsgaXg8ZW5kLTE7ICsraXgpIHsKICAgICAgICAgICAgICAgIGlmKGFycmF5W2l4XTw9cGl2KSB7CiAgICAgICAgICAgICAgICAgICAgICAgIGFycmF5LnN3YXAoc3RvcmUsIGl4KTsKICAgICAgICAgICAgICAgICAgICAgICAgKytzdG9yZTsKICAgICAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgYXJyYXkuc3dhcChlbmQtMSwgc3RvcmUpOwogCiAgICAgICAgcmV0dXJuIHN0b3JlOwp9ICAKICAKZnVuY3Rpb24gcXNvcnQoYXJyYXksIGJlZ2luLCBlbmQpCnsKICAgICAgICBpZihlbmQtMT5iZWdpbikgewogICAgICAgICAgICAgICAgdmFyIHBpdm90PWJlZ2luK01hdGguZmxvb3IoTWF0aC5yYW5kb20oKSooZW5kLWJlZ2luKSk7CiAKICAgICAgICAgICAgICAgIHBpdm90PXBhcnRpdGlvbihhcnJheSwgYmVnaW4sIGVuZCwgcGl2b3QpOwogCiAgICAgICAgICAgICAgICBxc29ydChhcnJheSwgYmVnaW4sIHBpdm90KTsKICAgICAgICAgICAgICAgIHFzb3J0KGFycmF5LCBwaXZvdCsxLCBlbmQpOwogICAgICAgIH0KfQogCmZ1bmN0aW9uIHF1aWNrX3NvcnQoYXJyYXkpIHsKICAgICAgICBxc29ydChhcnJheSwgMCwgYXJyYXkubGVuZ3RoKTsKfQogCmZ1bmN0aW9uIG1lYXN1cmVTb3J0T3JnKGFycmF5KSB7CiAgdmFyIHN0YXJ0ID0gbmV3IERhdGUoKTsKICBhcnJheS5zb3J0KCk7CiAgdmFyIGRpZmYgPSBuZXcgRGF0ZSgpIC0gc3RhcnQ7CiAgcmV0dXJuIHsgcmVzOiBhcnJheSwgZGlmZjogZGlmZiB9Owp9CiAKZnVuY3Rpb24gbWVhc3VyZVNvcnRDdXN0b20oYXJyYXkpIHsKICB2YXIgc3RhcnQgPSBuZXcgRGF0ZSgpOwogIHF1aWNrX3NvcnQoYXJyYXkpOwogIHZhciBkaWZmID0gbmV3IERhdGUoKSAtIHN0YXJ0OwogIHJldHVybiB7IHJlczogYXJyYXksIGRpZmY6IGRpZmYgfTsKfQogCiAgdmFyIGFycmF5T3JnID0gW107CiAgZm9yICh2YXIgaSA9IDA7IGkgPCA1MDAwOyBpKyspIHsKICAgIGFycmF5T3JnLnB1c2goTWF0aC5yYW5kb20oKSk7CiAgfQogIHZhciBhcnJheUN1c3RvbSA9IGFycmF5T3JnLnNsaWNlKDApOwogIHZhciBhcnJheU9yZyA9IGFycmF5T3JnLnNsaWNlKDApOwogIHZhciByZXNPcmcgPSBtZWFzdXJlU29ydE9yZyhhcnJheU9yZyk7ICAKICB2YXIgcmVzQ3VzdG9tID0gbWVhc3VyZVNvcnRDdXN0b20oYXJyYXlDdXN0b20pOwogIHZhciBlcXVhbCA9IHRydWU7CiAgZm9yICh2YXIgaSA9IDA7IGkgPCByZXNPcmcubGVuZ3RoOyBpKyspIHsKICAgIGlmIChNYXRoLmFicyhyZXNPcmdbaV0gLSByZXNDdXN0b21baV0pID4gMC4wMDAwMDAwMSkgewogICAgICBlcXVhbCA9IGZhbHNlOwogICAgICBicmVhazsKICAgIH0KICB9CiAgcHJpbnQoImxlbmd0aE9yZzogIiArIHJlc09yZy5yZXMubGVuZ3RoICsgJywgdGltZU9yZzogJyArIHJlc09yZy5kaWZmICsgJ21zXG4nICsgImxlbmd0aEN1c3RvbTogIiArIHJlc0N1c3RvbS5yZXMubGVuZ3RoICsgJywgdGltZUN1c3RvbTogJyArIHJlc0N1c3RvbS5kaWZmICsgJ21zXG4nICsgJ2VxdWFsOiAnICsgZXF1YWwpOwog