I get the following error message in my quickSort function:

TypeError: array is undefined

How do you write a quickSort function using the prototype ArrayList defined below?

function ArrayList() {
  this.items = [];
}
ArrayList.prototype.insert = function(item) {
  this.items.push(item);
}
ArrayList.prototype.toString = function() {
  return this.items.join();
}

//This is a function to create a non sorted array using the array function above

function createNonSortedRandomArray(size) {
  var elements = size;
  var array = new ArrayList();
  for (var i = elements; i > 0; i--) {
    array.insert(i);
  }
  return array;
}

swap = function(array, index1, index2) {
    var aux = array[index1];
    array[index1] = array[index2];
    array[index2] = aux;
}

// quickSort function begins here 

ArrayList.prototype.quickSort = function() {
  quick(this.array, 0, this.array.length - 1);
}

quick = function(array, left, right) {
  var index;

  if (array.length > 1) {
    index = partition(array, left, right);
    if (left < index - 1) {
      quick(array, left, index - 1);
    }
    if (index < right) {
      quick(array, index, right);
    }
  }
};

partition = function(array, left, right) {
  var pivot = array[Math.floor((right   left) / 2)],
    i = left,
    j = right;

  while (i <= j) {
    while (array[i] < pivot) {
      i  ;
    }
    while (array[j] > pivot) {
      j--;
    }
    if (i <= j) {
      swap(array, i, j);
      i  ;
      j--;
    }
  }
  return i;
};

// Execute code block here

var array2 = new createNonSortedRandomArray(33);
console.log(array2.toString());
array2.quickSort();
console.log(array2.toString());

CodePudding user response：

The problem is in the quickSort method, which accesses this.array, but the ArrayList instance does not have a property with that name. Looking at the constructor (at the top), the property is items. So change the method to:

ArrayList.prototype.quickSort = function() {
    quick(this.items, 0, this.items.length - 1);
//             ^^^^^          ^^^^^
}

This will fix the issue.

Remark: declare you variables always with var, let or const. You didn't do that for several functions defined with function expressions: swap, quick and partition. In strict mode it would not even parse without that keyword.

CodePudding user response：

A great source of inspiration for implementing various algorithms or data structures in JS for me is trekhleb's javascript-algorithms repository.

See Quicksort.