implement quicksort recursive function on prototype array

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());

I cannot call left.quickSort(); and right.quickSort(); JavaScript heap out of memory... what are the alternatives to write this code?? i browse a few online on the git but its different from to calculate the cost to run function.

alirabiee · Accepted Answer · 2017-08-26 06:07:16Z

2

I list below the fixed version of your code. The most important fixes include:

In partition the variable last_small contains the value of the element, but it is used as an index later in the loop.
In partition you are always comparing elements with the index 0 instead of the moving pivot element.
The quicksort function keeps partitioning and sorting 2-element arrays. Hence the memory overflow exception.
The original arrays is not reconstructed when done. Note that splice modifies the original array.

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() );

edited Aug 26, 2017 at 6:07

answered Aug 23, 2017 at 21:28

alirabiee

1,3067 silver badges14 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

En Hui Lim Over a year ago

can i ask this line of code? i dont understand [0, 0] refers to. self.splice.apply( self, [ 0, 0 ].concat( right.quickSort() ) );

alirabiee Over a year ago

[ 0, 0 ].concat( right.quickSort() ) prepends 0, 0 at the beginning of the sorted right partition. 0, 0 are the first two parameters to splice meaning add the items at position 0 and remove 0 items. Splice does not expect an array as its items parameter; by using apply you can directly pass your items array to splice instead of having to iterate over them and add them one by one.

En Hui Lim Over a year ago

hi i just did a test and if i use [1,10,6,5,4,3,7,9] is bugged it concat whenever the arrays form in atleast 2s.

alirabiee Over a year ago

I couldn't understand you really, but I tested it with that input and it still works.

En Hui Lim Over a year ago

when i put the input 1,10,6,5,4,3,7,9 the result is 1,3,4,5,7,6,9,10 :the 7 and 6 is not sorted.

phoenixqm · Accepted Answer · 2017-08-24 11:39:31Z

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() );

Collectives™ on Stack Overflow

implement quicksort recursive function on prototype array

2 Answers 2

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related