JavaScript Quicksort再帰

Question

JavaScriptのint配列のクイックソートアルゴリズムを実装しようとしています。 私のコードに問題があります。最初のいくつかのintはソートされますが、sortet配列の終わりにはソートされるべき配列の中で唯一の時間ですが、常に1つの整数が何度も置かれます。うまくいけば、誰かが私のせいを見つけるだろう。おかげさまで

function quicksort(array) { 
    var randomPlace = Math.round(Math.random() * array.length); 
    var pivotelement = array[randomPlace]; 
    left = new Array; 
    right = new Array; 
    for (var i = 0; i < array.length; i++) { 
     if (array[i] < pivot) { 
      left[left.length] = array[i]; 
     } else { 
      right[right.length] = array[i]; 
     } 
    } 
    if ((left.length == 0 || left.length == 1) && (right.length == 0 || right.length == 1)) { 
     return left.concat(right); 
    } else if (left.length == 0 || left.length == 1) { 
     return (left.concat((quicksort(right)))); 
    } else if (right.length == 0 || right.length == 1) { 
     return ((quicksort(left)).concat(right)); 
    } else { 
     return (quicksort(left)).concat((quicksort(right))); 
    } 
} 

Answer 1

あなたはrandomPlaceを誤って識別していると思います。 Math.round()を使用しているため、undefinedを何度か返します。 leftを初期化するときに使用し、また、次のコードを

を、そしてright：

代わりにこれを試してみてください

var left = new Array(); 
var right = new Array(); 

あなたは、いくつかのnamemingの混乱のほかに、私の完全なバイオリンhere

Answer 2

を見ることができます例えば、pivotelementとpivotとMath.roundとMath.floorの場合、left = []とright = [1, 1, 1]を常に返す[1, 1, 1]という問題に対処する必要があります。その場合、quicksort([1, 1, 1])を無期限に呼び出します。

この問題を解決するには、ランダムピボットと等しい場合、すべての要素がleftで、rightであることを確認する必要があります。その後rightを返し、quicksortを再度呼び出すことはありません。

function quicksort(array) { 
 
    var randomPlace = Math.floor(Math.random() * array.length), 
 
     pivot = array[randomPlace], 
 
     left = [], 
 
     right = [], 
 
     i; 
 

 
    for (i = 0; i < array.length; i++) { 
 
     (array[i] < pivot ? left : right).push(array[i]); 
 
    } 
 
    console.log(pivot, JSON.stringify(array), JSON.stringify(left), JSON.stringify(right)); 
 

 
    // prevent looping forever 
 
    if (!left.length && right.every(function (v) { return v === pivot; })) { 
 
     return right; 
 
    } 
 

 
    if (left.length <= 1 && right.length <= 1) { 
 
     return left.concat(right); 
 
    } 
 
    if (left.length <= 1) { 
 
     return left.concat(quicksort(right)); 
 
    } 
 
    if (right.length <= 1) { 
 
     return quicksort(left).concat(right); 
 
    } 
 
    return quicksort(left).concat(quicksort(right)); 
 
} 
 

 
console.log(quicksort([2, 7, 4, 8, 3, 11, 49, 20, 10, 1, 1, 1]));

.as-console-wrapper { max-height: 100% !important; top: 0; }

別の解決策は、3つの配列、小さな値のための1つの、等しい値のための1つのより大きな値のための1つに、アレイを分離することであろう。次に、より小さい配列と大きい配列だけをソートします。

function quicksort(array) { 
 
    var randomPlace = Math.floor(Math.random() * array.length), 
 
     pivotValue = array[randomPlace], 
 
     left = [], 
 
     pivot = [], 
 
     right = [], 
 
     i; 
 

 
    for (i = 0; i < array.length; i++) { 
 
     if (array[i] === pivotValue) { 
 
      pivot.push(array[i]); 
 
      continue; 
 
     } 
 
     (array[i] < pivotValue ? left : right).push(array[i]); 
 
    } 
 

 
    console.log(pivotValue, JSON.stringify(array), JSON.stringify(left), JSON.stringify(pivot), JSON.stringify(right)); 
 

 
    if (left.length <= 1 && right.length <= 1) { 
 
     return left.concat(pivot, right); 
 
    } 
 
    if (left.length <= 1) { 
 
     return left.concat(pivot, quicksort(right)); 
 
    } 
 
    if (right.length <= 1) { 
 
     return quicksort(left).concat(pivot, right); 
 
    } 
 
    return quicksort(left).concat(pivot, quicksort(right)); 
 
} 
 

 
console.log(quicksort([2, 7, 4, 8, 3, 11, 49, 20, 10, 1, 1, 1]));

.as-console-wrapper { max-height: 100% !important; top: 0; }