I am trying to find an error why quicksort does not work properly, I guess it is because of the swap function
function swap(a, b) {
return [b,a];
}
function partition(array, l, r) {
let pivot = array[(l + r) / 2];
let i = l;
let j = r;
while (i <= j) {
while (array[i] < pivot)
i++;
while (array[j] > pivot)
j++;
if(i >= j)
return j;
[array[i], array[j]] = swap([array[i]], array[j]);
}
}
function qsort(arr, left, right) {
if (left < right) {
let q = partition(arr, left, right)
qsort(arr, left, q);
qsort(arr, q + 1, right);
}
}
You should pass as a separated variable in swap function
[array[i], array[j]] = swap(array[i], array[j]);
correct solution will be
function swap(array, i, j) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
// call it like this
swap(array, index1, index2);
swap does have a problem, at least it should be swap(array[i], array[j]) instead of swap([array[i]], array[j]). but I think your sorting problem Not here, maybe you can try the following
function partition(array, l, r) {
let pivot = array[l];
let i = l;
let j = r;
while (i < j) {
while (i < j && array[j] >= pivot) --j;
arr[i] = arr[j];
while (i < j && array[i] <= pivot) i++;
arr[j] = arr[i];
}
arr[i] = pivot;
return i;
}
function qsort(arr, left, right) {
if (left < right) {
let q = partition(arr, left, right)
qsort(arr, left, q-1);
qsort(arr, q + 1, right);
}
}
const arr = [1, 7, 9, 8, 3, 2, 6, 0, 5, 4];
qsort(arr, 0, arr.length-1);
console.log(arr); // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]