Estoy tratando de observar mi clasificación de combinación recursiva cortando las matrices en cada paso.
function mergeSort(arr) { if(arr.length === 1) return arr; const mid = Math.floor(arr.length / 2); const leftArray = arr.slice(0, mid); const rightArray = arr.slice(mid, arr.length); console.log(leftArray, rightArray) return merge(mergeSort(leftArray), mergeSort(rightArray)); } function merge(leftArray, rightArray) { const sortedArray = []; while(leftArray.length > 0 && rightArray.length > 0) { if(leftArray[0] < rightArray[0]) { sortedArray.push(leftArray[0]); leftArray.shift(); } else { sortedArray.push(rightArray[0]); rightArray.shift(); } } return sortedArray.concat(leftArray).concat(rightArray); } Si ve el código anterior, estoy iniciando sesión leftArray y rightArray . Pero eso registra cada paso a la vez tan pronto como ejecuto el código. Para controlar la ejecución del código, convertí mi función mergeSort en una función de generador para que cada vez que ejecutara .next() pudiera ver el siguiente segmento.
function * mergeSort(arr) { if(arr.length === 1) return arr; const mid = Math.floor(arr.length / 2); const leftArray = arr.slice(0, mid); const rightArray = arr.slice(mid, arr.length); yield console.log(leftArray, rightArray); return merge(mergeSort(leftArray), mergeSort(rightArray)); } function merge(leftArray, rightArray) { const sortedArray = []; while(leftArray.length > 0 && rightArray.length > 0) { if(leftArray[0] < rightArray[0]) { sortedArray.push(leftArray[0]); leftArray.shift(); } else { sortedArray.push(rightArray[0]); rightArray.shift(); } } return sortedArray.concat(leftArray).concat(rightArray); } const list = [32, 12, 23, 52, 5, 16, 74, 21, 33, 55, 85]; const sort = mergeSort(list); sort.next(); // I expected [32, 12], [23, 52, 5] sort.next(); // [32, 12] and so on...Resultó que el resultado no fue lo que esperaba. ¡Le agradecería mucho que me aconsejara sobre el uso de la función de generador!
En la ordenación por fusión, la matriz se divide en matrices más pequeñas hasta que su tamaño es 1. Después de esto, fusiona las matrices más pequeñas de tal manera que la matriz recién creada también se ordena.
Para comprender la recursión, puede rastrear todos los niveles de recursión con sangría. Por ejemplo:
const log = (level, data) => { var s = "" for (i = 0; i < level; i++) { s += " "; } console.log(s + data); } const merge = (left, right) => { const result = []; while(left.length && right.length){ if(left[0] <= right[0]){ result.push(left.shift()); }else{ result.push(right.shift()); } } while(left.length) result.push(left.shift()); while(right.length) result.push(right.shift()); return result; } const mergeSort = (array, level) => { log(level, "Start " + array); if(array.length < 2) { log(level, "Finish " + array); return array; } const middle = Math.floor(array.length / 2); log(level, "middle element " + array[middle]) const leftArr = array.slice(0, middle); const rightArr = array.slice(middle, array.length); var result = merge(mergeSort(leftArr, level + 1), mergeSort(rightArr, level + 1)); log(level, "Finish " + result); return result; };llamar a la función con valor de nivel como 1.