javascript - 快速排序问题 - 没有得到正确的结果

Question

我正在研究 Quicksort2 HackerRank 上的问题。我不知道它要我如何输出解决方案。

我尝试在创建排序数组时控制台记录它们，一个排序数组数组和一个转换为字符串的数组数组。从 processData 函数返回似乎什么都不做。

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);
}

我期待它与 HackerRank 的期望输出相匹配。

Answer 1

您的实现存在一些问题:

以下是任务描述中的引述:

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

但是，您正在尝试打印最终排序的数组 sortedArrays 而不是问题所述的每个步骤的子数组。因此，在返回子数组 newArr 之前打印它。不要忘记使用 join 格式化输出。

另一段引述:

There will be two lines of input:

the size of the array

the n numbers of the array

您的 processData 需要一个经过解析的输入，也就是一个它可以使用的数组。如果它接收到原始输入(2 行数据)，那么它们应该被相应地解析。例如，它们可以被解析如下:

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

因此您的固定代码如下所示:

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;
    }
}