1

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());
    });     
}
Herman Jansson
  • 164
  • 1
  • 8
  • 3
    Javascript doesn't have multithreading, even if you use async functions like promise.all, the async functions are not executed at the same time – Patrick Hund Apr 15 '19 at 19:37
  • Check out this talk, it explains how the event loop in JS works really well: https://youtu.be/8aGhZQkoFbQ – Patrick Hund Apr 15 '19 at 19:39
  • Promises are a helper to deal with managing already asynchronous tasks. There is nothing asynchronous about your sort, and using promises does not make anything run in parallel. – Bergi Apr 15 '19 at 20:26
  • @Bergi I am using promise in an already asynchronous function right? I thought ```js Promise.all([func(), func()]) ``` was supposed to execute async functions in parallel. – Herman Jansson Apr 16 '19 at 10:26
  • 1
    @PatrickHund thanks for fast answer :) I understand now – Herman Jansson Apr 16 '19 at 10:27
  • @HermanJansson But your `func()` is not actually asynchronous - there is only synchronous code inside your quicksort. No timeouts, file io, network io etc. – Bergi Apr 16 '19 at 17:57

0 Answers0