I have written a async quicksort in javascript, have previous done the same in c++. But my async quicksort here wont sort faster than my syncronous one. Does anyone understand why this is happening?
Ive tried to use Promise.all to execute async functions at the same time
If anyone could explain why this is happening i would be pleased ! :D
Array.prototype.swap = function(a, b) {
let temp = this[a];
this[a] = this[b];
this[b] = temp;
}
Array.prototype.partition = function(begin, end){
let left = begin + 1;
let right = end - 1;
while(true) {
while(left < right && !(this[right] < this[begin]))--right;
while(left < right && this[left] < this[begin]) ++left;
if(left == right) break;
this.swap(left, right);
}
if(this[begin] < this[left]) {
return begin;
}
this.swap(begin, left);
return left;
}
Array.prototype.asyncQuickSort = async function(begin = 0, end = this.length){
if(end - begin < 2) return this;
let pivot = end - 1;
this.swap(pivot, begin);
let partitionPoint = this.partition(begin, end);
await Promise.all([this.asyncQuickSort2(begin, partitionPoint), this.asyncQuickSort2(partitionPoint + 1, end)]);
return this;
};
Array.prototype.asyncQuickSort2 = async function(begin, end) {
if(end - begin < 2) return this;
let pivot = end - 1;
this.swap(pivot, begin);
let partitionPoint = this.partition(begin, end);
this.syncQuickSort(begin, partitionPoint);
this.syncQuickSort(partitionPoint + 1, end);
};
Array.prototype.syncQuickSort = function(begin, end){
if(begin == undefined) {
begin = 0; end = this.length;
}
if(end - begin < 2) return this;
let pivot = end - 1;
this.swap(pivot, begin);
let partitionPoint = this.partition(begin, end);
this.syncQuickSort(begin, partitionPoint);
this.syncQuickSort(partitionPoint + 1, end);
return this;
};
Array.prototype.generate = function(amount){
while(this.length > 0) this.pop();
for(let i = 0; i < amount; i++)
this.push(Math.floor((Math.random() * 100) + 1));
return this;
};
Array.prototype.sorted = function(){
for(let i = 0; i < this.length - 2; i++) {
if(this[i] > this[i + 1]) return false;
}
return true;
};
Array.prototype.copy = function() {
const arr = [];
this.forEach(value => arr.push(value));
return this;
};
const arr = [].generate(500000);
const syncArr = arr.copy();
const asyncArr = arr.copy();
exec();
function exec() {
let start = new Date();
asyncArr.asyncQuickSort().then((res) => {
console.log('async: ', new Date() - start, 'ms is sorted: ', res.sorted());
start = new Date();
syncArr.syncQuickSort();
console.log('sync: ', new Date() - start, 'ms is sorted: ', syncArr.sorted());
});
}