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());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.
A great source of inspiration for implementing various algorithms or data structures in JS for me is trekhleb's javascript-algorithms repository.
See Quicksort.