CODEWITHSUNDEEP
javascriptalgorithmquicksort
Eojo
Eojo

Reputation: 35

Quicksort Problem - not getting the correct result

I'm working on the Quicksort2 problem on HackerRank. I can't figure out how it wants me to output the solution.

I've tried to console.log the sorted arrays as they're created, an array of the sorted arrays and an array of the arrays converted to strings. Returning from the processData function seems to do nothing. 

function checkSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] > arr[i + 1]) return false;
    }
    return true;
}

function processData(input) {
    let sortedArrays = [];
    quickSort(input);

    function quickSort(input) {

        if (input.length <= 1) return input;

        let pivot = [input[0]];
        let left = [], right = [];
        for (let i = 1; i < input.length; i++) {
            input[i] < pivot ? left.push(input[i]) : right.push(input[i]);
        }

        let newArr = quickSort(left).concat(pivot, quickSort(right));
        if (checkSort(newArr)) sortedArrays.push(newArr);
        return newArr;
    }
    console.log(sortedArrays);
}

I'm expecting it to match HackerRank's desired output.

Upvotes: 1

Views: 297

Answers (1)

Anatolii
Anatolii

Reputation: 14660

There're a couple of issues with your implementation:

Below is a quote from the task description:

In this challenge, print your array every time your partitioning method finishes, i.e. whenever two subarrays, along with the pivot, are merged together.

However, you're trying to print the final sorted array sortedArrays rather than a subarray for each step as the problem states. So, print the subarray newArr before returning it. Don't forget to format the output using join.

Another quote:

There will be two lines of input:

the size of the array

the n numbers of the array

Your processData expects a parsed input aka an array that it can work with. If it receives the raw input (2 lines of data) then they should be parsed accordingly. for instance, they could be parsed as below:

...
function processData(input) {
    var lines = input.split('\n')
    var len = lines[0]
    var arr = lines[1].split(' '); 
...

And so your fixed code could look as follows:

function processData(input) {
    var lines = input.split('\n')
    var len = lines[0]
    var arr = lines[1].split(' ');
    quickSort(arr);
        function quickSort(input) {

        if (input.length <= 1) return input;

        let pivot = [input[0]];
        let left = [], right = [];
        for (let i = 1; i < input.length; i++) {
            input[i] < pivot ? left.push(input[i]) : right.push(input[i]);
        }

        let newArr = quickSort(left).concat(pivot, quickSort(right));
        // print the subarray once the partitioning for this step has finished
        console.log(newArr.join(' '))
        return newArr;
    }
}

Upvotes: 2

Related Questions