Tengo una implementación de clasificación de combinación en Javascript y en golang. Funciona correctamente en golang, sin embargo, en javascript parece estar siempre desactivado por 1. No he encontrado ningún error notable. Agradecería cualquier idea de por qué está fallando
Yo he tratado:
for que comience en leftStartMath.floor a Math.ceil y Math.roundstart hasta middle-1 y desde el middle hasta el end function mergeSort(arr) {
merge(arr, 0, arr.length - 1, []);
}
function merge(arr, start, end, temp) {
if (start >= end) {
return;
}
const middle = Math.floor((start + end) / 2);
merge(arr, start, middle, temp);
merge(arr, middle + 1, end, temp);
mergeHalves(arr, start, end, temp);
}
function mergeHalves(arr, leftStart, rightEnd, temp) {
const leftEnd = Math.floor((leftStart + rightEnd) / 2);
const rightStart = leftEnd + 1;
const size = rightEnd - leftStart + 1;
let left = leftStart;
let right = rightStart;
let index = left;
while (left <= leftEnd && right <= rightEnd) {
if (arr[left] <= arr[right]) {
temp[index] = arr[left];
left++;
} else {
temp[index] = arr[right];
right++;
}
index++;
}
while (left <= leftEnd) {
temp[index] = arr[left];
index++;
left++;
}
while (right <= rightEnd) {
temp[index] = arr[right];
index++;
right++;
}
for (let i = 0; i < size; i++) {
arr[i] = temp[i];
}
}
Caso de prueba:
const arr = [2, 1, 3, 5, 6, 2, 7];
mergeSort(arr);
//coming back as [1, 2, 3, 5, 6, 2, 7]
expect(arr).toEqual([1, 2, 2, 3, 5, 6, 7]);
El problema está en este bucle:
for (let i = 0; i < size; i++) {
arr[i] = temp[i];
}
Esto está mal de dos maneras:
Esto asigna valores a los elementos en arr[0..size-1] , pero en general ese no es el rango que se fusiona aquí. Debería apuntar a arr[leftStart..rightEnd] .
temp tampoco recopiló sus valores a partir del índice 0. Sin embargo, eso hubiera sido más lógico, por lo que se debe corregir cómo se inicializa el index antes en esa función.
Aquí están las líneas corregidas:
let index = 0; // not leftStart!
/*
... the rest of your code ...
and finally:
*/
for (let i = 0; i < size; i++) {
arr[leftStart + i] = temp[i];
}