Empresas
Empleos
  • Sobre nosotros
  • Soluciones
    • Publicación de vacantes
      Publica tu vacante y recibe candidatos calificados en 48h.
    • Evaluación de candidatos
      500+ pruebas técnicas y psicológicas, más anti-fraude.
    • Headhunting
      Búsqueda ejecutiva a la medida de principio a fin.
    • Nómina + EOR
      Dispersión de nómina y EOR en más de 15 países de LATAM.
  • Precios
  • Empleos

0

260
Vistas
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 Respuestas
Responde la pregunta

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 Denunciar

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 Denunciar
Responde la pregunta
Encuentra empleos remotos

¡Descubre la nueva forma de encontrar empleo!

Top de empleos
Top categorías de empleo
Empresas
Publicar vacante Precios Comercial
Legal
Términos y condiciones Política de privacidad
© 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Recomiéndame algunas ofertas
Necesito ayuda