Estaba tratando de implementar el algoritmo de ordenación por combinación en JavaScript sin métodos integrados como slice(), splice(), etc. No funciona exactamente como deseo. ¿Me pueden ayudar a averiguar dónde está escondido el error? Obteniendo la salida [3, 5, 5, 3, 7] en lugar de [3, 5, 5, 7, 8].
// Merge Sort implementation // sort implementation function sort(arr, start, mid, end) { // Creation and filling the temp arrays let lArray = []; let rArray = []; for (let i = 0; i <= mid - start; i++) { lArray[i] = arr[start + i]; } for (let j = 0; j <= end - mid - 1; j++) { rArray[j] = arr[mid + 1 + j]; } // Sorting and updating current array let i = 0; let j = 0; let k = start; while (i < lArray.length && j < rArray.length) { if (lArray[i] < rArray[j]) { arr[k] = lArray[i]; i++; k++; } else { arr[k] = rArray[j]; j++; k++; } } // Handling last element in lArray or rArray i < lArray.length ? arr[k] = lArray[i] : arr[k] = rArray[j]; } // Recursive Merge Sort function recursiveMergeSort(arr, start, end) { if (start < end) { let mid = Math.floor(((end) + start) / 2); //console.log(start, end, mid); recursiveMergeSort(arr, start, mid); recursiveMergeSort(arr, mid + 1, end); sort(arr, start, mid, end); } } function mergeSort(arr) { let start = 0; let end = arr.length - 1; recursiveMergeSort(arr, start, end); return (arr) } console.log(mergeSort([5, 8, 3, 7, 5]));// Handling last element in lArray or rArray no es correcto.
Después de fusionar matrices, debe verificar los descansos y copiar la cola sin tratar si existe
while (i < lArray.length) { arr[k] = lArray[i]; i++; k++; } while (j < rArray.length) { arr[k] = rArray[j]; j++; k++; }Reemplazar el operador ternario por este código da resultados correctos para datos dados
Ejemplo de una versión algo optimizada de clasificación de combinación de arriba hacia abajo. Realiza una asignación única de una matriz de trabajo y utiliza un par de funciones mutuamente recursivas para cambiar la dirección de fusión para cada nivel de recursividad. Toma alrededor de 1/4 de segundo clasificar 1 millón de números enteros pseudoaleatorios en mi sistema:
// merge sort top down 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 } }