Empresas
Empregos
  • Sobre nós
  • Soluções
    • Publicação de vagas
      Publique sua vaga e receba candidatos qualificados em 48h.
    • Avaliações de candidatos
      Mais de 500 testes técnicos e psicológicos, mais anti-fraude.
    • Headhunting
      Busca executiva personalizada do início ao fim.
    • Folha de Pagamento + EOR
      Dispersão de folha e EOR em mais de 15 países da LATAM.
  • Preços
  • Empregos

0

259
Visualizações
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 Respostas
Responde à pergunta

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 Relatório

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 Relatório
Responde à pergunta
Encontrar trabalhos remotos

Descubra a nova forma de encontrar um emprego!

melhores empregos
Principais categorias de trabalho
Empresas
Postar vaga Preços Comercial
Jurídico
Termos e Condições Política de privacidade
© 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Recomende algumas ofertas para mim
Preciso de ajuda