Estoy tratando de escribir un algoritmo de clasificación de combinación en javascript, pero veo que no funciona. Estoy tomando una matriz de muestra [9,1,5,3] y tratando de ordenarla. Pero me está dando un resultado incorrecto, pero la consola me muestra [3, undefined, undefined, 5] . No puedo averiguar por mí mismo dónde está yendo mal. Alguien me puede ayudar en esto
function merge(arr, start, mid, end) { const result = []; let first = start; let index = start; let midNext = mid + 1; while (first <= mid && midNext <= end) { if (arr[first] <= arr[midNext]) { result[index++] = arr[first++] } else { result[index++] = arr[midNext++] console.log(result) } while (first <= mid) { result[index++] = arr[first++] console.log(result) } while (midNext <= end) { result[index++] = arr[midNext++] console.log(result) } } for (let i = 0; i <= end; i++) { arr[i] = result[i]; } console.log(arr) } function mergeSort(arr, start, end) { if (start == end) { return start; } let midIndex = Math.floor(start + (end - start) / 2); mergeSort(arr, start, midIndex); mergeSort(arr, midIndex + 1, end); merge(arr, start, midIndex, end) }Clasificación de combinación de arriba hacia abajo de javascript ejecutable. Tenga en cuenta que la mayoría de las bibliotecas utilizan una variación de ordenación por combinación de abajo hacia arriba, generalmente una combinación de ordenación por inserción y combinación de abajo hacia arriba. La clasificación de combinación de arriba hacia abajo es principalmente para fines académicos.
Este ejemplo realiza una asignación única de una segunda matriz y usa un par de funciones mutuamente recursivas (cada una llama a la otra), sortatoa(), sortatob() para cambiar la dirección de fusión según el nivel de recursividad. Clasificará 1 millón de enteros en un poco menos de 250 ms en mi sistema.
function merge(a, b, bgn, mid, end) { var i = bgn // left: a[bgn,mid) var j = mid // right: a[mid,end) var k = bgn // index for b[] while(true){ if(a[i] <= a[j]){ // if left <= right b[k++] = a[i++] // copy left if(i < mid) // if not end of left continue // continue back to while do // else copy rest of right b[k++] = a[j++] while(j < end) break // and break } else { // else left > right b[k++] = a[j++] // copy right if(j < end) // if not end of right continue // continue back to while do // else copy rest of left b[k++] = a[i++] while(i < mid) break // and break } } } function sortatob(a, b, bgn, end) { // sort a to b if ((end-bgn) < 2){ b[bgn] = a[bgn] return } var mid = Math.floor(bgn + (end - bgn) / 2) sortatoa(a, b, bgn, mid) sortatoa(a, b, mid, end) merge(a, b, bgn, mid, end) } function sortatoa(a, b, bgn, end) { // sort a to a if ((end-bgn) < 2) return var mid = Math.floor(bgn + (end - bgn) / 2) sortatob(a, b, bgn, mid) sortatob(a, b, mid, end) merge(b, a, bgn, mid, end) } function mergesort(a) { // entry function if(a.length < 2) return var b = new Array(a.length) // allocate temp array sortatoa(a, b, 0, a.length) // start with sort a to a } var a = new Array(1000000) for (i = 0; i < a.length; i++) { a[i] = parseInt(Math.random() * 1000000000) } console.time('measure') mergesort(a) console.timeEnd('measure') for (i = 1; i < a.length; i++) { if(a[i-1] > a[i]){ console.log('error') break } }El error en tu código está aquí: for (let i = 0; i <= end; i++)
Cuando copie la matriz de result nuevamente en arr , debe escribir:
for (let i = start; i <= end; i++) { arr[i] = result[i - start]; }Así que eché un vistazo al problema y escribí el algoritmo mergesort de la manera más concisa que pude. Comparándolo con su solución dada, puede ver que su función mergeSort ya es bastante buena. Creo que complicaste demasiado la fusión. En la parte de fusión, querrá comparar el siguiente elemento que no se ha agregado a la matriz fusionada, lo que puede lograr con un ciclo while. Por lo tanto, no necesita un índice de inicio, medio y final en la función de combinación.
function mergeSort(arr) { const half = arr.length / 2; if (arr.length <= 1) { return arr; } const left = arr.splice(0, half); const right = arr; return merge(mergeSort(left), mergeSort(right)); } function merge(left, right) { let sortedArr = []; while (left.length && right.length) { if (left[0] < right[0]) { sortedArr.push(left.shift()); } else { sortedArr.push(right.shift()); } } return [...sortedArr, ...left, ...right]; } console.log(mergeSort([213,12323,53,12,453,231,12]));Si tiene preguntas específicas con respecto a mi respuesta, no dude en comentar.