Encuentre mi implementación de clasificación rápida a continuación en 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);La salida es la siguiente:
[ 1, 2, 3, 5, 7, 9, 6, 4 ]El último conjunto de elementos no se ha ordenado correctamente. ¿Alguien podría echar un vistazo y decirme el problema?
Gracias
El problema es que su función de partition realizará como máximo 2 intercambios. Esto no puede estar bien.
El proceso de intercambio (el primero en su código) debe repetirse hasta que i haya llegado a j .
No es el problema, pero como la función está mutando A , ese debería ser un parámetro de la función, esa es la mejor práctica.
Aquí hay una actualización de su función, con un script de prueba debajo que prueba la implementación de 1000 matrices que se barajan aleatoriamente:
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");Está a mitad de camino, está iterando lo bajo y lo alto, pero ambos junto con el intercambio deben estar en un ciclo que va desde lo bajo hasta lo alto, hasta que lo alto no se superponga a lo bajo, el ciclo continuará. y una vez que se rompe el ciclo, obtuvo su índice de poner el pivote, también necesita tener un índice de pivote que lo ayudará al final a intercambiar la j con el índice de pivote; así que debería ser así
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;}espero esta ayuda