CODEWITHSUNDEEP
javascriptalgorithmtypescriptquicksort
gyc
gyc

Reputation: 4360

Trying to draw each quicksort iteration on canvas

I'd like to see live quicksort iterations on a canvas.

Here is the small project I'm working on.

The problem I'm having is that it draws the initial shuffled state and the sorted state without the steps in between.

  quickSort(initArray, metaLeft, metaRight) {
    if (initArray.length <= 1) { 
        return initArray;
    } else {
        var left = [];
        var right = [];
        var newArray = [];
        var pivot = initArray.pop();
        var length = initArray.length;

        for (var i = 0; i < length; i++) {
            if (initArray[i] <= pivot) {
                left.push(initArray[i]);
            } else {
                right.push(initArray[i]);
            }
        }
        // console.log([].concat(metaLeft, left, pivot, right, metaRight));
        this.wait();
        this.draw([].concat(metaLeft, left, pivot, right, metaRight));
        var sortedLeft = this.quickSort(left, metaLeft, [pivot].concat(right, metaRight))
        var sortedRight = this.quickSort(right, metaLeft.concat(sortedLeft, pivot), metaRight)
        return newArray.concat(sortedLeft, pivot, sortedRight);
    }
  }

I believe it is because of quicksort being recursive but I don't know why and how I could make this work.

The console.log right before the wait / draw functions apparently shows the correct steps I need to draw.

Upvotes: 0

Views: 53

Answers (1)

Ry-
Ry-

Reputation: 225054

The issue is that your call to the wait() function doesn’t do any waiting. You can make quickSort() async too:

async quickSort(initArray, metaLeft, metaRight) {
    if (initArray.length <= 1) { 
        return initArray;
    }

    let left = [];
    let right = [];
    let pivot = initArray.pop();
    let length = initArray.length;

    for (let i = 0; i < length; i++) {
        if (initArray[i] <= pivot) {
            left.push(initArray[i]);
        } else {
            right.push(initArray[i]);
        }
    }

    await this.wait();
    this.draw([].concat(metaLeft, left, pivot, right, metaRight));
    let sortedLeft = await this.quickSort(left, metaLeft, [pivot].concat(right, metaRight))
    let sortedRight = await this.quickSort(right, metaLeft.concat(sortedLeft, pivot), metaRight)
    return [].concat(sortedLeft, pivot, sortedRight);
}

updating calls to it to use promises accordingly:

this.quickSort(this.lines, [], []).then(sortedLines => {
    this.lines = sortedLines;
});

Converting it to an in-place quicksort would also help make things more natural, getting rid of metaLeft and metaRight and allowing you to ignore the final promise.

Upvotes: 1

Related Questions