3

こんにちは、クイックソートプログラム用にこのロジックを試しました。しかし、このコードを変換してインターバルモードを設定する必要があり、プロセス全体を段階的にカバーする必要があります。このロジックを setinterval Program に改善するのを手伝ってください。現在、再帰モードになっていると思います。

function quicksort(arr)
{
    if (arr.length == 0)
        return [];

    var left = new Array();
    var right = new Array();
    var pivot = arr[0];

    for (var i = 1; i < arr.length; i++) {
        if (arr[i] < pivot) {
           left.push(arr[i]);
        } else {
           right.push(arr[i]);
        }
    }

    return quicksort(left).concat(pivot, quicksort(right));
}
4

1 に答える 1

1

最初にクイックソートを非再帰形式 (反復クイックソート) に変換してから、setInterval を使用して for ループを置き換え、元のクイックソートを「setInterval モード」に変換することができます。

Stoimen のブログからの反復クイックソートを次に示します (元の再帰的クイックソートは同じソースから来ていると思います)。ではなく、継続渡しスタイルでコールバックを使用するように、少し変更したことに注意してくださいreturn。

function qsort(arr, ret)
{
    var stack = [arr];
    var sorted = [];

    while (stack.length) {

        var temp = stack.pop(), tl = temp.length;

        if (tl == 1) {
            sorted.push(temp[0]);
            continue;
        }
        var pivot = temp[0];
        var left = [], right = [];

        for (var i = 1; i < tl; i++) {
            if (temp[i] < pivot) {
                left.push(temp[i]);
            } else {
                right.push(temp[i]);
            }
        }

        left.push(pivot);

        if (right.length)
            stack.push(right);
        if (left.length)
            stack.push(left);

    }

    ret(sorted);
}

この方法で関数を呼び出すことができます (例):

qsort([3,7,1,4,2,5], function(sortedarray) { console.log(sortedarray); });

この反復クイックソートを「setInterval モード」に変換するには、関数内の for ループを setInterval の呼び出しに置き換えることができます (この Stackoverflow の投稿と同様)。

を使用したクイックソートの最終バージョンは次のsetIntervalとおりです。

function qsort(arr, ret)
{
    var stack = [arr];
    var sorted = [];
    var intervalId = 0;

    intervalId = setInterval(function() {
        if (stack.length) { 
            var temp = stack.pop(), tl = temp.length;

            if (tl == 1) {
                sorted.push(temp[0]);
                return;
            }
            var pivot = temp[0];
            var left = [], right = [];

            for (var i = 1; i < tl; i++) {
                if (temp[i] < pivot) {
                    left.push(temp[i]);
                } else {
                    right.push(temp[i]);
                }
            }

            left.push(pivot);

            if (right.length)
                stack.push(right);
            if (left.length)
                stack.push(left);           
        } 
        else if (sorted.length == arr.length) {
            clearInterval(intervalId);
            ret(sorted);
        }
    }, 0);      
}

ここで何が起こるかというと、元の配列の一部がスタックに追加され (これがパーティショニング ステップです)、個別に並べ替えられます。呼び出すたびsetIntervalに、配列の異なる部分をソートしています (元の再帰的クイックソートでは、すべてのクイックソート呼び出しが配列の異なる部分を扱っていました)。setIntervalソートされた配列が元の配列と同じサイズになると、ソートを停止する (つまり、呼び出しを停止するように指示する) ことに注意してください。それがretコールバックを呼び出すときです。

于 2012-10-27T08:05:27.623 に答える