JavaScriptへのquickselect

Question

私はJavaScriptに変換するためのクイックソルト実装のさまざまなバージョンのすべてについてインターネットを精査しており、その多くは正常に移植できません。

私は、これはJavaやC++、または掲載の人々が壊れている例についてのニュアンスを知らない私が原因であるかどうかを把握することができていません。

パフォーマンスは最適化されていませんが、読みやすく論理的です。

私はこの実装に着いたが、それは動作しないことに気づいた。

出力は（原因Math.random（）への可能性が高い）ランダムであるが、私はアルゴに従うように、私はこの次のテストケースとイライラ。

出力は999、3、100、2、および1000から、私はロジックに従うことができない範囲と本当に誰かが、このような不安定な結果を与えることを何が起こっているかを説明いただければ幸いです。

function swap(array, idxA, idxB) { 
    var temp = array[idxA] 
    array[idxA] = array[idxB] 
    array[idxB] = temp 
} 

function partitionStart(arr, left, right, pivotIdx) { 
    var storeIdx = left, pivotVal = arr[pivotIdx]; 
    swap(arr, pivotIdx, right) 
    for (var i = left; i <right; i++) { 
    if (arr[i] < pivotVal) { 
     swap(arr, storeIdx, i) 
     storeIdx++ 
    } 
    } 
    swap(arr, pivotIdx, right); 
    return storeIdx; 
} 

function quickSelectLoop(arr, k) { 
    var pivotIndex, pivotNewIdx, pivotDist, 
    left = 0, right = arr.length-1 

    while(true) { 
    pivotIndex = Math.floor(Math.random()*arr.length) 
    pivotNewIdx = partitionStart(arr, left, right, pivotIndex) 
    pivotDist = pivotNewIdx - left 

    if (pivotDist === k) { 
     return arr[pivotNewIdx-1] 
    } else if (k < pivotDist) { 
     right = pivotNewIdx -1 
    } else { 
     k -= pivotDist+1 
     left = pivotNewIdx + 1 
    } 
    } 
} 

var test2 = [1000,999,1,2,3,100,105] 
console.log(quickSelectLoop(test2, 4)) 

100はquickSelect（TEST2、4）=> 100から

予想出力は、コレクション内の4番目の最小要素である

Answer 1

現在の実装では、複数の欠陥を有します。私はあなたの現在のコードのアイデアが本当に理解できないので、私はあなたのコードをどのように理解したのかを説明し、修正したものを提供しようとします。

partitionStart - leftからrightまでのインデックスのパーティション部分は、pivotIdxの部分をセパレータとして使用します。分離のインデックスsepIdxを返します。sepIdxより前のすべての項目はピボット項目よりも小さく、その後のすべての項目はそれ以上です。

quickSelectLoop - 指定された配列からk番目の最小のアイテムを選択します。 関数は、leftとrightの間のすべての項目が任意の順序であるが、配列のleft .. rightの最小項目であるという不変条件に依存します。

{A,B,C} = {0,1,2}ので、arr = [2,1,0,4,3]とarr = [0,1,2,3,4]が共に正しい次いでleft = 0、right = 2、初期アレイ= {0,1,2,3,4}、 arr = [A,B,C,x,x]、もし。解説付き

修正されたコード：

function partitionStart(arr, left, right) { 
    // You were passing pivotIdx here, I think that selecting pivotIdx 
    // should be this method's responsibility, so I moved the code here 
    // Also you were taking pivotIdx ignoring left and right - fixed that 
    var pivotIdx = Math.floor(Math.random() * (right - left + 1)) + left; 
    var storeIdx = left, pivotVal = arr[pivotIdx] 
    // You had a swap of pivot with the right here, 
    // which allowed you to traverse 1 item less in a cycle, 
    // but with the cost of one line of code - removed that 
    for (var i = left; i <= right; i++) { 
    if (arr[i] < pivotVal) { 
     swap(arr, storeIdx, i) 
     storeIdx++ 
    } 
    } 
    // Here was a strange swap of pivot back from right to its position, 
    // now it is not needed. 
    return storeIdx; 
} 

function quickSelectLoop(arr, k) { 
    var pivotDist; 
    var left = 0, right = arr.length - 1;  
    while(right !== left) { 
    // Maintaining: left <= k <= right, while enclosing left to right 
    pivotDist = partitionStart(arr, left, right)   
    // You were returning arr[k] here if pivotDist == k, 
    // but that is incorrect considering function's invariant - 
    // we can't make such a conclusion unless left == right. 
    // I corrected that check - it is now located in the while loop. 
    if (k < pivotDist) { 
     right = pivotDist - 1; 
    } else { 
     // You were adding 1 here, which is incorrect, 
     // because item at pivotDist may be the answer as well. 
     left = pivotDist; 
    } 
    }  

    // left == right, and we maintained 'left <= k <= right', so we have an answer 
    return arr[k] 
} 

jsfiddle