1

トレーニング目的で、一連の並べ替えアルゴリズムを JavaScript で実装しました。私の実装は、ヒープソートを除いて、整数および単一文字の文字列配列のソートに成功しています。

私の実装では、並べ替えられた配列を返すときに最小の数字を最後に配置することを除いて、配列を正しく並べ替えます。

私は CS の学生でも卒業生でもありませんし、プログラミングの経験もあまりありません。私は読み取り/試行/失敗の方法で学習していますが、これを正しく機能させることができませんでした。

コードとその結果をこの段落の下に置きます。最後に、このウィキペディアの記事の疑似コードを実装のリファレンスとして使用していることを付け加えておきます。

function heapSort(intl)
{
    var l   = intl.length,
        end = l - 1,
        swap;
    intl = _heapify(intl,l);

    while(end>0)
    {
        swap      = intl[0];
        intl[0]   = intl[end];
        intl[end] = swap;
        --end;
        intl = _siftDown(intl, 0, end);
    }

    return intl;
}


function _heapify(intl, l)
{
    var start = (l - 2) / 2;
    while(start >= 0)
    {
        intl = _siftDown(intl, start, l-1);
        --start;
    }
    return intl;
}

function _siftDown(intl, start, end)
{
    var root = start,
        child, swap, swapr;
    while(root*2+1 <= end)
    {
        child = root * 2 + 1;
        swap = root;
        if(intl[swap] < intl[child])
            swap = child;
        if(child+1 <= end && intl[swap]<intl[child+1])
            swap = child + 1;
        if(swap!=root)
        {
            swap       = intl[root];
            intl[root] = intl[swap];
            intl[swap] = swap;
            root       = swap;
        }else
        {
            return intl;
        }
    }
    return intl;
}


x =
[24,5,896,624,437,5,6,4,37,45,654];
y =
["a","b","r","s","t","e","q","u","q"];

console.log(heapSort(x),"\n",heapSort(y));

nodejs 経由でコードを実行します。

$ node sort.js
[ 5, 5, 6, 24, 37, 45, 437, 624, 654, 896, 4 ]
[ 'b', 'e', 'q', 'q', 'r', 's', 't', 'u', 'a' ]

コードを変更してエラーの場所を見つけようとしましたが、見つかりませんでした。誰が問題がどこにあるかを知ることができますか? 前もって感謝します。

4

1 に答える 1

1

私は2つのエラーを見ました:

  1. _heapify関数では、 が奇数でない場合、変数はstart整数ではありません。l

    var start = Math.floor( ( l - 2 ) / 2 );

  2. _siftDown関数では、配列の2つの要素を効果的に交換する代わりに使用しましたswap:swapr

    swapr      = intl[root];  // <-- Here swapr instead of swap
intl[root] = intl[swap];
intl[swap] = swapr;       // <-- Here swapr instead of the 1st occurrence of swap
root       = swapr;       // <-- Here swapr instead of swap
于 2012-11-28T09:34:44.417 に答える