Business
Jobs
  • About Us
  • Solutions
    • Job Postings
      Post your job and receive qualified candidates in 48h.
    • Candidate Assessments
      500+ technical and psychological tests, plus anti-fraud.
    • Headhunting
      Tailor-made executive search from start to finish.
    • Payroll + EOR
      Payroll dispersal and EOR across 15+ LATAM countries.
  • Pricing
  • Jobs

0

257
Views
Quick Sort algorithm implementation in javascript

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

about 4 years ago · Juan Pablo Isaza
2 answers
Answer question

0

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");

about 4 years ago · Juan Pablo Isaza Report

0

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

about 4 years ago · Juan Pablo Isaza Report
Answer question
Find remote jobs

Discover the new way to find a job!

Top jobs
Top job categories
Business
Post vacancy Pricing Sales
Legal
Terms and conditions Privacy policy
© 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Show me some job opportunities
There's an error!