2

クイックソート アルゴリズムの仕組みを学ぼうとしています。私はこれをCLRアルゴリズムの本を読んでやっています。同じ数値の配列に対してアルゴリズムがどのように機能するかを理解できないようで、オンラインで例を見つけることができませんでした。たとえば、この場合のクイックソート アルゴリズムの進行は次のようになります。

{5h, 5i, 5j, 5k, 5m, 5n}

ここで、文字 (h、i、j、k、m、n) は、さまざまな 5 を区別するためのものです。

4

2 に答える 2

1

あのいまいましい本は、賢明な変数名を使用していれば、はるかに簡単に消化できたかもしれませんが、すべての数学に使用される通常の1文字の変数規則から逸脱したくなかったと思います.

私は関数名と変数名を保持し、コードをほとんどコピーしようとしました。これには、彼らが使用する「配列は 1 から始まる」規則も含まれます。非ランダム ピボット バージョンを模倣しました。

デモ: http://jsfiddle.net/p7R99/

または、次を .html ファイルに入れるだけです

<pre id="out">
</pre>

<script>
function QUICKSORT(A, p, r) {
    if (p < r) {
        var q = PARTITION(A, p, r);
        output("q=" + q + " and A=" + arr(A) + "\n");
        QUICKSORT(A, p, q - 1);
        QUICKSORT(A, q + 1, r);
    }
}

function PARTITION(A, p, r) {
    var x = A[r];
    var i = p - 1;
    for (var j = p; j < r - 1; j++) {
        if (intval(A[j]) <= intval(x)) {
            i = i + 1;
            swap(A, i, j);
        }
    }
    swap(A, i + 1, r);
    return i + 1;
}

function intval(str) {
    return parseInt(str, 10);
}



function swap(A, i, j) {
    var tmp = A[i];
    A[i] = A[j];
    A[j] = tmp;
}

function output(msg) {
    var ele = document.getElementById("out");
    ele.innerHTML += msg;
}
function arr(A) {
    return A.slice(1).join(" ");
}


var A = [undefined, "5h", "5i", "5j", "5k", "5m", "5n"];
QUICKSORT(A, 1, A.length);
</script>

結果

q=1 and A= 5i 5j 5k 5m 5n 5h
q=6 and A= 5i 5j 5k 5m 5h 5n
q=4 and A= 5i 5j 5m 5k 5h 5n
q=2 and A= 5j 5i 5m 5k 5h 5n
于 2012-10-31T02:32:21.497 に答える
0

これは、クイックソートで O (n^2) のパフォーマンスが得られる数少ないケースの 1 つです (あまり慎重に実装しないと) パーティションの 1 つが空になる可能性があるためです。

事前に入力について知っていて、それらがほとんど同じである場合は、カウントソートまたは3方向クイックソートを検討することをお勧めします

于 2012-10-30T17:59:12.953 に答える