JavaScriptクイックソートの無限再帰？

Question

ここには私が書いたquicksortコードです。ベースケースに届かないため機能しません。ピボットをrとlにコンソールに記録すると、ソート関数が何回呼び出されても同じままです。したがって、引数l,rが本当にデータとして関数に渡されないのだろうかと思います。なぜそれが起こったのですか？

function sort(data){ 
    if(data.length < 2){ 
     return data; 
    } 
    else{ 
     var l = []; 
     var r = []; 
     var pivot = parseInt(data.length/2); 
     for(i=0; i<data.length; i++){ 
      if(data[i] > data[pivot]){ 
       r.push(data[i]); 
      } 
      else{ 
       l.push(data[i]); 
      } 
     } 
     return sort(l).concat(sort(r)); 
    } 
} 

Answer 1

ここでの問題は、パーティショニングのステップが必ずしも入力配列を縮小しないということです。たとえば、[1、2]をソートしようとするとどうなるかをトレースしましょう。この場合、ピボット要素は要素2になります.1> 2が偽であるため、1がリストlに追加されます。 2> 2が偽であるので、2がリストlに追加されます。その結果、リストlの再帰呼び出しは、元の呼び出しとまったく同じ引数を持ち、無限再帰を引き起こします。

この問題を解決するには、小さい値、等しい値、大きい値の3つのリストに入力を分割してみてください。この新しいバージョンを明示的グループ、自分のリストに等しい要素が

function sort(data){ 
    if (data.length < 2){ 
    return data; 
    } else { 
    var l = []; 
    var r = []; 
    var e = []; 
    var i = 0; 
    var pivot = (data.length/2) | 0; 

    for(i = 0; i < data.length; i++) { 
     if (data[i] > data[pivot]) { 
     r.push(data[i]); 
     } else if (data[i] < data[pivot]) { 
     l.push(data[i]); 
     } else { 
     e.push(data[i]); 
     } 
    } 
    return sort(l).concat(e, sort(r)); 
    } 
} 

ので、それらを再帰的に再帰呼び出しのどちらかによってソートされていません。このコードは、ここで示されています。重複した要素も正常に処理します。

希望すると便利です。

Answer 2

JavaScriptはオブジェクトを参照渡しします（配列もオブジェクトです）。値渡しの場合は、hereのようにスプライス関数を使用する必要があります。

これにより、データのコピーが多数作成されることに注意してください。おそらくネイティブのsort（）関数を使いたいと思うでしょう。

Answer 3

配列の最大値をピボット要素として選択すると、dataのすべての値は配列lになり、いずれもrになりません。したがって、再帰は決して止まらなくなります（l、rおよびpivotを同じ値に保ちます）。 これが脳の訓練でない限り、data.sort()を使用するとより良い仕事をするはずです。 ;）