Closed
Description
Thanks for your great work and for second edition. I'm stuck on Quick Sort section.
Code:
function ArrayList() {
var array = []
var swap = function(array, index1, index2) {
var aux = array[index1]
array[index1] = array[index2]
array[index2] = aux
}
this.insert = function(item) {
array.push(item)
}
this.toString = function() {
return array.join()
}
this.quickSort = function() {
quick(array, 0, array.length - 1);
};
var 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); // {5}
}
if (index < right) {
quick(array, index, right); // {7}
}
}
};
var 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;
};
}
function createNonSortedArray(size) {
var array = new ArrayList();
for (var i = size; i > 0; i--) {
array.insert(i);
}
return array;
}
var array = new ArrayList()
array.insert(3)
array.insert(5)
array.insert(1)
array.insert(6)
array.insert(4)
array.insert(7)
array.insert(2) // [3, 5, 1, 6, 4, 7, 2]
array.quickSort()
console.log(array.toString())My own step by step explanation of work with array [3, 5, 1, 6, 4, 7, 2] (Identical to array from quick sort section in book):
// first step:
// index = partition([3, 5, 1, 6, 4, 7, 2], 0, 6) = 5
// if (left < index - 1) = if (0 < 5 - 1) = if (0 < 4)[true] : quick([3, 5, 1, 2, 4, 7, 6], 0, 4)
// second step:
// index = partition([3, 5, 1, 2, 4, 7, 6], 0, 4) = 1
// if (left < index - 1) = if (0 < 1 - 1) = if (0 < 0)[false]
// if (index < right) = if (1 < 4)[true] : quick([1, 5, 3, 2, 4, 7, 6], 1, 4)
// third step:
// index = partition([1, 5, 3, 2, 4, 7, 6], 1, 4) = 3
// if (left < index - 1) = if (1 < 3 - 1) = if (1 < 2)[true] : quick([1, 2, 3, 5, 4, 7, 6], 1, 2)Next the part that is confusing to me:
// fourth step:
// index = partition([1, 2, 3, 5, 4, 7, 6], 1, 2) = 2
// if (left < index - 1) = if (1 < 2 - 1) = if (1 < 1)[false] // here false and we can not use line {5} of algorithm
// if (index < right) = if (2 < 2)[false] // and here false and we can not use line {7} of algorithm
// what happens next?how in this case we are going to indexes 3 and 4 of array and then to 5 and 6?