クイックソートの再帰

Question

私は現在、javascriptの配列にquicksortを実装しようとしています。私は全体のレイアウトを持っていますが、何らかの理由で再帰が機能していません。それはコードの2番目の反復のために働いたようですが、その後、それはちょうどうんざりするようです。私が間違ったことを確信していない。

function main() { 
 
    var type = "quicksort" 
 
    var testArray = [9, 6, 5, 0, 8, 2, 4, 7]; 
 

 
    quickSort(testArray, 0, testArray.length - 1); 
 
    for (var i = 0; i < testArray.length; i++) { 
 
    console.log(testArray[i]); 
 
    } 
 

 
} 
 

 
function quickSort(array, start, end) { 
 
    var type = "quicksort" 
 
    var pIndex; 
 

 
    if (start <= end) { 
 
    pIndex = partition(array, start, end); 
 
    quickSort(array, start, pIndex - 1); 
 
    quickSort(array, pIndex + 1, end); 
 
    } 
 

 

 
} 
 

 
function partition(array, start, end) { 
 
    var x = end; 
 
    console.log(start); 
 
    var i = start - 1; 
 
    var temp; 
 

 
    for (var j = 0; j < end - 1; j++) { 
 
    if (array[j] <= x) { 
 
     i++; 
 
     temp = array[j]; 
 
     array[j] = array[i]; 
 
     array[i] = temp; 
 
     temp = 0; 
 

 

 
    } 
 
    } 
 

 
    temp = array[i + 1]; 
 
    array[i + 1] = array[x]; 
 
    array[x] = temp; 
 
    temp = 0; 
 

 
    return i + 1; 
 
} 
 

 
main();

Answer 1

間違いが

@関数クイックソート

//if (start <= end) 
    // should be 
    if (start < end) 

@関数のパーティション

//for (var j = 0; j <= end - 1; j++) { 
// if (array[j] <= x) { 
// Should be 
for (var j = start; j <= end - 1; j++) { 
    if (array[j] <= array[x]) { 

次のコードは動作するはずです。

function main() { 
    var type = "quicksort" 
    var testArray = [9, 6, 5, 0, 8, 2, 4, 7]; 

    quickSort(testArray, 0, testArray.length - 1); 
    for (var i = 0; i < testArray.length; i++) { 
    console.log(testArray[i]); 
    } 

} 

function quickSort(array, start, end) { 
    var type = "quicksort"; 
    var pIndex; 

    if (start < end) { 
    pIndex = partition(array, start, end); 
    quickSort(array, start, pIndex - 1); 
    quickSort(array, pIndex + 1, end); 
    } 


} 

function partition(array, start, end) { 
    var x = end; 
    console.log(start); 
    var i = start - 1; 
    var temp; 

    for (var j = start; j <= end - 1; j++) { 
    if (array[j] <= array[x]) { 
     i++; 
     temp = array[j]; 
     array[j] = array[i]; 
     array[i] = temp; 
     temp = 0; 
    } 
    } 

    temp = array[i + 1]; 
    array[i + 1] = array[x]; 
    array[end] = temp; 
    temp = 0; 

    return i + 1; 
} 

main(); 

希望すると助かります！

Answer 2

いくつかのミス：

if (start <= end) {範囲は最初から始まるときfor (var j = 0は、0から始まるどの場合start = end

を治療する必要はありませんか？

if (array[j] <= x) {インデックスと商品の値を比較しますか？