Please find my quicksort implementation below in javascript.
const A = [4, 6, 2, 5, 7, 9, 1, 3];
const partition = function(l, h) {
let pivot = A[l];
let i = l;
let j = h;
while(A[i] <= pivot) {
i++;
}
while(A[j] > pivot) {
j--;
}
if (i < j) {
let temp = A[i];
A[i] = A[j];
A[j] = temp;
}
let temp1 = A[l];
A[l] = A[j];
A[j] = temp1;
return j;
}
const quickSort = function (l, h) {
if (l < h) {
let piIdx = partition(l, h);
console.log('the pidx is ', piIdx);
quickSort(l, piIdx - 1);
quickSort(piIdx + 1, h);
}
}
quickSort(0, A.length - 1);
console.log('array after quicksort call ', A);
The output is as below:
[ 1, 2, 3, 5, 7, 9, 6, 4 ]
The last set of elements haven't been sorted properly. Could anyone please have a look and let me know the problem.
thanks
The problem is that your partition function will at most perform 2 swaps. This cannot be right.
The process of swapping (the first one in your code) should be repeated until i has arrived at j.
Not the problem, but as the function is mutating A, that should be a parameter of the function -- that is best practice.
Here is an update of your function, with a test script below it that tests the implementation for 1000 arrays that are randomly shuffled:
const partition = function(A, l, h) { // A is parameter
let pivot = A[l];
let i = l;
let j = h;
while (true) { // Keep going
while(A[i] <= pivot) {
i++;
}
while(A[j] > pivot) {
j--;
}
if (i >= j) break; // All done
let temp = A[i];
A[i] = A[j];
A[j] = temp;
}
A[l] = A[j];
A[j] = pivot; // We already know A[l], no need for temp
return j;
}
const quickSort = function (A, l, h) { // A is parameter
if (l < h) {
let piIdx = partition(A, l, h);
quickSort(A, l, piIdx - 1);
quickSort(A, piIdx + 1, h);
}
}
// Test the implementation
function shuffle(a) {
let i = a.length;
while (i) {
let j = Math.floor(Math.random() * i--);
[a[i], a[j]] = [a[j], a[i]];
}
}
const A = [...Array(50).keys()]; // is sorted
const ref = A.toString(); // string to compare solution with
for (let attempt = 0; attempt < 1000; attempt++) {
shuffle(A);
quickSort(A, 0, A.length - 1);
if (A.toString() != ref) {
console.log('Error: array not sorted after quicksort call ', ...A);
break;
}
}
console.log("all tests done");
You are halfway there , you are iterating the low and high but those both along with there swap needs to be in a loop that goes from low all the way to high meaning until high does not overlap low , the loop will keep on going . and once the loop breaks you got your index of putting the pivot you also need to have a pivot index that will help you at the end to swap the j with the pivot index; so it should be like this
var pivotIndex=l;
while(i<j){
while(A[i] <= pivot) {
i++;
}
while(A[j] > pivot) {
j--;
}
if (i < j) {
let temp = A[i];
A[i] = A[j];
A[j] = temp;
}
let temp1 = A[l];
A[l] = A[j];
A[j] = temp1;
}
[nums[pivotIndex],nums[j]]=[nums[j],[nums[pivotIndex]]
return j;}
I hope this help