2

残念ながら、これまで自分でコーディングしたことはありません。私の実装は、「日付」フィールドのソートに基づいてカスタムクラスで動作します。はい、組み込みのJavascriptソートを使用してコンパレータ関数を指定できることを十分に認識していますが、それは私が興味を持っていることではありません。

現在、逆ソートされたリストから始めて、「target_sort」（QuickSort）を呼び出した後、あまりよくソートされていないリストを取得します。

コード：

function target_sort_wrapper(array) {
    target_sort(array, array.length, 0, array.length);
}


//Quicksort to swap around targets based on dates
//"array" is DDATA, where DDATA[i] are targets
function target_sort(array, length, left, right) {
    if (length < 2) {
        return;
    }
    var pivotIndex = choosePivot(array, length); //returns the index    

    partition(array, pivotIndex, left, right);

    target_sort(array, pivotIndex, 0, pivotIndex - 1);
    target_sort(array, pivotIndex, pivotIndex + 1, array.length);

}

function partition(array, pivotIndex, left, right) {
    //first, put the pivot as the first element to make things easier
    array.swap(pivotIndex, 0);
    var pivot = array[0];
    var i = left + 1;
    for (var j = left + 1; j < right; j++) {
        if (dateValue(array[j].date) < dateValue(pivot.date)) {
            //dateValue converts stuff like "Jun18" into 618, to numerically compare
            array.swap(i, j);
            i = i + 1;
        }
    }
    //don't forget to put pivot back where it belongs
    array.swap(left, i - 1);
}

function choosePivot(array, length) {
    return Math.floor(Math.random() * length); //0 (inclusive) to length (exclusive) 
}

    Array.prototype.swap = function (i, j) {
        var temp = this[i];
        this[i] = this[j];
        this[j] = temp;
        return this;
    }

そして、これが出力です。最初に逆ソートされたリストが出力され、次に「target_sort」の結果が出力されます。

Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 
============================================================= 
Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun25 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun25 Jun25 Jun25 Jul05 Jun25 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jun25 Jul06 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jul06 Jul06 Jun25 Jul06 Jun25 Jun25 Jun25 Jun25 Jul05 Jun25 Jul05 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul05 Jul05 Jul05 Jul06

そこに到達しているような気がしますが、まだ何かがおかしいです。

私はこれに数日間立ち往生しているので、助けてくれてありがとう。

乾杯。

4

2 に答える 2

7

再帰呼び出しは壊れています：

target_sort(array, pivotIndex, 0, pivotIndex - 1);

明らかなことの1つはpivotIndex、両方のパーティションの長さとして渡すことですが、これは意味がありません。

もう1つは、インデックス作成が壊れていることです。ご覧のとおり、左側のインデックスは0ですが、2番目の再帰レベルにいて、上位レベルの右側のパーティションの左側のパーティションを取得したい場合は、明らかに当てはまりません。

もう1つ、ピボットチューザーはアレイについて知る必要はありません。

function choosePivot(length)

ヒント：プログラミングは推測ゲームではありません。始める前に、「変数」が正確に何を意味するかを決定してください。長さ、左、右は何ですか？例：正しいインデックスは包括的ですか（パーティションの一部を指しているのか、それともそのすぐ先を指しているのか）。次に、紙と鉛筆を選び、適切なインデックスと長さを見つけます。私を信じてください、あなたがそれについて注意深く考えるほど、あなたはより早く終わります。デバッグには多くの時間が無駄になります。次に、正しい方向に進んでいることを確認するために、実装に小さなおもちゃの配列を使用し、console.logメッセージを追加して何が起こっているかを確認します。

于 2012-07-24T19:55:59.033 に答える
2

正しいバージョンを作成しました。ヒントをくれたKarolyに感謝します。概要：

  • 長さに関しては何もするべきではありませんが、左右に
  • 私は常に再帰呼び出しに不適切なピボットを選択していました（ここでも、左右に配置する必要があり、サブアレイの適切な範囲内にある必要があります）

コード：

function target_sort_wrapper(array) {
    target_sort(array, 0, array.length);
}


//Quicksort to swap around targets based on dates
//"array" is DDATA, where DDATA[i] are targets
function target_sort(array, left, right) {
    if ((right-left) < 2) {
        return;
    }

    var pivotIndex = choosePivot(left, right); //returns the index  

    pivotIndex = partition(array, pivotIndex, left, right);

    target_sort(array, left, pivotIndex);
    target_sort(array, pivotIndex+1, right);

}

function partition(array, pivotIndex, left, right) {
    //first, put the pivot as the first element to make things easier
    var pivot = array[pivotIndex];
    array.swap(pivotIndex, left);
    var i = left + 1; 
    for(var j = left + 1; j < right; j++) {
        //if (array[j] > pivot) { } //do nothing, satisfies invariant
        if (dateValue(array[j].date) < dateValue(pivot.date)) {
        //if (array[j] < pivot) {
            array.swap(i, j);
            i = i + 1; 
        }
    }
    //don't forget to put pivot back where it belongs
    array.swap(left, i-1);
    return (i-1);
}

function choosePivot(left, right) {
    return (left + Math.floor(Math.random() * (right-left)));

}

Array.prototype.swap = function(i, j) {
    var temp = this[i];
    this[i] = this[j];
    this[j] = temp;
    return this;
}
于 2012-07-24T22:15:43.307 に答える