プロトタイプ配列のクイックソート再帰関数を実装しています

Question

Array.prototype.quickSort = function() { 
let self = this; 
let len = self.length; 
let pivot_pos; 
let result = [] 
if (len < 2) { 
    return self 
} 
pivot_pos = self.partition(); 
let left = self.splice(0, pivot_pos), 
right = self.splice(0); 


error --> left.quickSort(); 
error --> right.quickSort(); 

console.log(left); 
console.log(right); 
//right_pivot_pos = right.partition(); 

return this; 
} 

Array.prototype.partition = function() { 
    let arr = this; 
    let pivot_pos = Math.floor((arr.length-1)/2); 
let last_small = arr[0] 
let i; 
//console.log(`before this[0] ${this[0]} and before this[pivot_pos] 
${this[pivot_pos]}`); 
[arr[pivot_pos], arr[0]] = [arr[0], arr[pivot_pos]]; 
//console.log(`this[0] ${this[0]} and this[pivot_pos] 
${this[pivot_pos]}`); 

for (i=1;i<arr.length; i++) { 
    if(arr[i]<arr[0]) { 
    //[this[i], this[num]] = [this[num], this[i]]; 
    let tmp = arr[last_small]; 
    arr[last_small] = arr[i]; 
    arr[i] = tmp; 
    last_small++; 
    } 
    } 
[arr[0], arr[last_small-1]] = [arr[last_small-1], arr[0]]; 
return last_small; 
} 

let sandbox = [1,2,6,5,4,3,7,9]; 
console.log(sandbox.quickSort()); 

私はleft.quickSort（）を呼び出せません。とright.quickSort（）; JavaScriptヒープメモリ不足...このコードを書くための代替手段は何ですか？私はgit上でいくつかのオンラインを参照するが、関数を実行するためのコストを計算するためには異なる。

Answer 1

Array.prototype.swap = function (i, j) { 
    var tmp = this[i]; 
    this[i] = this[j]; 
    this[j] = tmp; 
}; 

Array.prototype._quicksort = function(A, i, j) { 
    if (i >= j) { 
     return; 
    } 
    if (i+1 == j) { 
     if (A[i] > A[j]) { 
      A.swap(i,j); 
     } 
     return; 
    } 

    var p = Math.floor((i+j)/2); 
    A.swap(i, p); 

    var l = i; 
    var r = j; 
    while (l <= r) { 
     if (A[l] <= A[i]) { 
      l++; 
     } else if (A[r] > A[i]) { 
      r--; 
     } else { 
      A.swap(l, r); 
      l++; 
      r--; 
     } 
    } 

    p = l-1; 
    A.swap(i, p); 

    Array.prototype._quicksort(A, i, p-1); 
    Array.prototype._quicksort(A, p+1, j); 
} 

Array.prototype.quickSort = function() { 
    Array.prototype._quicksort(this, 0, this.length-1); 
    return this; 
}; 

var A = [ 1, 10, 6, 2, 8, 5, 4, 3, 7, 9 ]; 
console.log(A.quickSort()); 

Answer 2

私はあなたのコードの固定版の下にリストします。最も重要な修正が含まれます：partition変数last_smallで

• は、要素の値が含まれていますが、それは後に、ループ内の指標として使用されています。
• partitionでは、移動ピボット要素の代わりに常に要素をインデックス0と比較しています。
• quicksort関数は、2要素配列の分割とソートを継続します。したがって、メモリオーバーフローの例外です。
• 元の配列は、完了すると再構成されません。 spliceは元の配列を変更することに注意してください。

Array.prototype.quickSort = function() { 
 
    var self = this; 
 

 
    if (self.length < 2) { 
 
     return self 
 
    } 
 

 
    var pivot_pos = self.partition(); 
 

 
    if (self.length > 2) { 
 
     var left = self.splice(0, pivot_pos); 
 
     var right = self.splice(0); 
 

 
     self.splice.apply(self, [ 0, 0 ].concat(right.quickSort())); 
 
     self.splice.apply(self, [ 0, 0 ].concat(left.quickSort())); 
 
    } 
 

 
    return this; 
 
}; 
 

 
Array.prototype.swap = function (i, j) { 
 
    var tmp = this[i]; 
 
    this[i] = this[j]; 
 
    this[j] = tmp; 
 
}; 
 

 
Array.prototype.partition = function() { 
 
    var self = this; 
 
    var pivot_pos = Math.floor((self.length - 1)/2); 
 
    var last_small_i = 0; 
 

 
    self.swap(last_small_i, pivot_pos); 
 

 
    for (var i = 1; i < self.length; i++) { 
 
     if (self[ i ] < self[ last_small_i ]) { 
 
      self.swap(last_small_i, i); 
 
      last_small_i++; 
 
      
 
      if(i != last_small_i) { 
 
       self.swap(last_small_i, i); 
 
      } 
 
     } 
 
    } 
 

 
    return last_small_i; 
 
}; 
 

 
var sandbox = [ 1, 10, 6, 5, 4, 3, 7, 9 ]; 
 
console.log(sandbox.quickSort());