1

Javascriptでソートアルゴリズムをコーディングしようとしています。疑似コードは私のリンクにあります。これは私の Go Playground リンクです。 http://play.golang.org/p/wQwO6Wvd7b

ご覧のとおり、他の言語でも動作します。(Python、C、C++、Ruby、Go で同じコードを試してみましたが、すべて完璧に動作しました。) Javascript でまったく同じことをしましたが、動作せず、理由がわかりません。前回の投稿で Chris に感謝します: Javascript Sorting。割り当て失敗プロセスのメモリ不足エラー

Javascript のコードが再帰でインデックス制限を超えていることがわかりましたが、Javascript でそれが可能である理由と方法がわかりませんが、他の言語はコーディング時に適切な仕事をします。Javascript と再帰の基本的なものが確実に欠けています。体は私が理解するのを助けることができますか？（宿題ではなく、独学です）私はJavascriptを初めて使用します。

Javascript で並べ替えを行う必要はないと思いますが、何が間違っているのか知りたいです。

以下は、エラーチェックを目的とした私のコードです。 

  var arr = [-1, 5, 7, 4, 0, 1, -5];
  console.log("Unsorted Array:", arr);
  console.log("# of elements in array:", arr.length)

  function Partition(arr, first_index, last_index) {
        console.log("---")  
        console.log("# of elements in array:", arr.length)
        console.log("First index is", first_index);
        console.log("Last index is", last_index);
        console.log("---")  
        var x = arr[last_index];
        var i = first_index - 1;

        for (var j = 0; j < arr.length-1; j++) {
              if (j > 100) {
                    console.log("Looping way too much.");
                    return;
              }
              if (arr[j] <= x) {
                    i += 1;
                    console.log("Swap index:", i, j);
                    var temp_1 = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp_1;
              }
        }
        console.log("Swap index:", (i+1), last_index);
        var temp_2 = arr[i+1];
        arr[i+1] = arr[last_index];
        arr[last_index] = temp_2;

        return i+1;
  }

  function QSort(arr, first_index, last_index) {
        console.log("QuickSort index:", first_index, last_index);

        if (first_index < last_index) {
              var mid = Partition(arr, first_index, last_index);
              QSort(arr, first_index, mid-1);
              QSort(arr, mid+1, last_index);
        }
  }

  QSort(arr, 0, arr.length-1);
  console.log("Sorted Array:", arr);

そして、これがループしすぎている理由を以下に推測しています。再帰で何か間違ったことをしていることがわかりました。

配列の要素数: 8
最初のインデックスは 2
最後のインデックスは 6

スワップ インデックス: 2 0
スワップ インデックス: 3 2
スワップ インデックス: 4 3
スワップ インデックス: 5 4
スワップ インデックス: 6 5
スワップ インデックス: 7 6
スワップ インデックス: 8 6
クイックソート インデックス: 2 7

配列の要素数: 9
最初のインデックスは 2
最後のインデックスは 7

と続きます

4

3 に答える 3

1

これが間違って書かれているため、これが他の言語でどのように機能するかはわかりません。パーティション メソッドのループは、配列全体で動作しますが、実際には、動作するように指示された部分 (first_index と last_index の間) でのみ動作する必要があります。

このコード行:

for (var j = 0; j < arr.length-1; j++)

次のようにする必要があります。

for (var j = first_index; j < last_index; j++)
于 2013-09-06T22:51:16.290 に答える
1

関数内の for ループは次のPartitionように記述します。

for (var j = first_index; j < last_index; j++) {...}

それ以外の

for (var j = 0; j < arr.length-1; j++) {...}

0from toをループarr.length-1すると、単に交換するのではなく、元の配列内に新しい要素が作成されます。

于 2013-09-06T22:54:01.960 に答える
0

SPOILER ALERT - このフィドルには、動作するバージョンのクイックソートがあります。私はあなたのバージョンにちょっと苦労したので、自分で書きました。

クイックソートのようなアルゴリズムでは、エラーが発生する可能性が高くなります (多くの場所が 1 つずれているなど)。

一般的な提案として、配列を渡すだけで呼び出すクイックソート メソッドを作成することをお勧めします。

function quick_sort(array) {
    qsort(array, 0, array.length);
    console.log(array);
}

お役に立てれば

http://jsfiddle.net/mwa4G/

http://en.literateprograms.org/Quicksort_(JavaScript)

于 2013-09-06T22:41:28.680 に答える