Acabo de empezar a codificar y he intentado varias horas para averiguar por qué no obtendría una salida de terminal. ¿Alguna suposición?
const unsortedArray = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9]; let initialIndex, finalIndex, i, j; function quickSort(initialIndex, finalIndex, unsortedArray) { if(initialIndex >= finalIndex) { return unsortedArray; } let key = initialIndex; let i = initialIndex + 1; let j = finalIndex; while(i <= j) { while (unsortedArray[i]<=unsortedArray[key] && i<finalIndex) { i++; } while (unsortedArray[j]>=unsortedArray[key] && j>initialIndex) { j--; } if(i > j) { let temp = unsortedArray[initialIndex]; unsortedArray[initialIndex] = unsortedArray[j]; unsortedArray[j] = unsortedArray[initialIndex]; } else { let temp = unsortedArray[i]; unsortedArray[i] = unsortedArray[j]; unsortedArray[j] = temp; } } quickSort(initialIndex,j-1,unsortedArray); quickSort(j+1,finalIndex,unsortedArray); return unsortedArray } function showSortedArray (unsortedArray) { quickSort(0, unsortedArray.length-1, unsortedArray); console.log(unsortedArray); } showSortedArray(unsortedArray);He encontrado otras formas (creando dos nuevas matrices y agregando izquierda y derecha), pero quiero tener éxito en este método.
El ordenamiento rápido más simple que he logrado encontrar es este:
function quicksort(arr) { if (arr.length == 0) return []; var left = [] var right = [] var pivot = arr[0]; for (var i = 1; i < arr.length; i++) { if (arr[i] < pivot) { left.push(arr[i]); } else { right.push(arr[i]); } } return quicksort(left).concat(pivot, quicksort(right)); }Y una versión para matrices 2D:
function quicksort_2D(options) { /* options: arr - arr to sort sortcol - column position to sort on sorttype - */ if (options.arr.length == 0) return []; var left = [] var right = [] var pivot = options.arr[0][options.sortcol]; for (var i = 1; i < options.arr.length; i++) { if (options.arr[i][options.sortcol] < pivot) { left.push(options.arr[i]); } else { right.push(options.arr[i]); } } var pivotarr=[options.arr[0]] var retval = quicksort_2D({arr: left, sortcol: options.sortcol, sorttype: options.sorttype}).concat(pivotarr, quicksort_2D({arr: right, sortcol: options.sortcol, sorttype: options.sorttype})); return retval }Su función entrará en un ciclo infinito cada vez que i y j sean iguales al valor finalIndex.
El problema es esta línea aquí:
while (unsortedArray[i]<=unsortedArray[key] && i<finalIndex) { i++; } Debido a que tiene i<finalIndex , nunca llego a finalIndex, lo que debería porque es un valor válido que puede necesitar ser intercambiado (esto contrasta con el valor de clave/índice inicial que es el pivote/límite y se maneja de manera diferente) .
Podrías cambiarlo a esto:
while (unsortedArray[i]<=unsortedArray[key] && i<=finalIndex) {Pero ahora obtendrá un error de matriz fuera de los límites después de que pase finalIndex, por lo que debe cambiarlo a esto:
while (i<=finalIndex && unsortedArray[i]<=unsortedArray[key]) {Entonces ahora verificará primero el límite de la matriz, antes de intentar acceder a la matriz. Esto debería solucionar tus problemas.