Solucionado (ver solução)
Solucionado
(ver solução)
1
resposta

[Dúvida] Código não funciona fora do exemplo da aula.

Tentei aplicar o seguinte código numa lista grande de arrays mas ao rodá-lo no terminal, ele aparentemente fica rodando infinitamente e não retorna nada:

const numbers = require('./arrayNumber');

function mergeSort(array) {
        while(array.length > 1) {
            const half = Math.floor(array.length/2);
            const firstHalf = array.slice(0, half);
            const secondHalf = array.slice(half, array.length);
            
            const sortedFirstHalf = mergeSort(firstHalf);
            const sortedSecondHalf = mergeSort(secondHalf);

            array = sortLists(sortedFirstHalf, sortedSecondHalf);
        }
    return array;
}

function sortLists(firstArray, secondArray) {
    let firstArrayCurrentIndex = 0;
    let secondArrayCurrentIndex = 0;

    const newArray = [];
    let newArrayCurrentIndex = 0;

    while(firstArrayCurrentIndex < firstArray.length && 
        secondArrayCurrentIndex < secondArray.length) {

        let firstArraySwap = firstArray[firstArrayCurrentIndex];
        let secondArraySwap = secondArray[secondArrayCurrentIndex];

        if (firstArraySwap < secondArraySwap) {
            newArray[newArrayCurrentIndex] = firstArraySwap;
            firstArrayCurrentIndex++;
        } else {
            newArray[newArrayCurrentIndex] = secondArraySwap;
            secondArrayCurrentIndex++;
        }

        newArrayCurrentIndex++;
    }
    while(firstArrayCurrentIndex < firstArray.length) {
        newArray[newArrayCurrentIndex] = firstArray[firstArrayCurrentIndex]; 
        firstArrayCurrentIndex++;
        newArrayCurrentIndex++;
    }

    while(secondArrayCurrentIndex < secondArray.length) {
        newArray[newArrayCurrentIndex] = secondArray[secondArrayCurrentIndex]; 
        secondArrayCurrentIndex++;
        newArrayCurrentIndex++;
    }
    return newArray;
}

console.dir(mergeSort(numbers), {'MaxArrayLength': null});

A array em questão é:

const arrayNumber = [
  337839545, 869801530, 789210918, 815913754, 369843237, 529236267, 155545353,
  477233828, 191350405, 854952642, 865936121, 299339437, 898148692, 744964025,
  334248266, 911944373, 474460497, 698167816, 260148469, 285922972, 552707486,
  293820662, 397991156, 209103732, 495611048, 677978791, 224189921, 828198856,
  382692356, 515880575, 189419296, 341790324, 342786811, 389493536, 738288780,
  201253495, 143959007, 899524766, 560203276, 142059978, 546298226, 395724608,
  966963109, 315052290, 156533440, 783511929, 294657660, 933375011, 924952992,
  994342574, 556727471, 368187020, 658462022, 645648248, 588984251, 971201648,
  972908564, 186637721, 608999633, 738037039, 322380887, 148368654, 559676732,
  255200192, 562461438, 988742186, 198792880, 662382036, 507827302, 910180335,
  635731236, 975362464, 587215533, 150042776, 600377683, 810763640, 838924292,
  723140096, 672039840, 851310002, 267922736, 757729176, 590720881, 661592306,
  338420845, 551317003, 120434116, 317269092, 696695972, 467810999, 352587863,
  130381505, 846594231, 506721021, 773587022, 914412659, 602201778, 159051350,
  319844539, 887292176, 252021254, 503778513, 882751688, 255955702, 988868731,
  564857756, 642012631, 240240395, 516128720, 474140502, 320580806, 787856856,
  264036911, 986199827, 862537114, 159957264, 456270171, 135935323, 874422267,
  808538891, 319105703, 368923075, 325950274, 321721181, 314874903, 982096359,
  695517181, 854187878, 808865897, 495430718, 570641769, 654082949, 896028134,
  958826755, 552555671, 258801831, 286694042, 274354010, 595760474, 672292650,
  755274024, 846629765, 735439117, 318648568, 874679935, 697895104, 412589593,
  843616285, 374006080, 957489929, 481696562, 773103047, 674863314, 170480731,
  271911522, 372399505, 415361920, 549009773, 524621192, 333318095, 745277535,
  781850383, 543254355, 641948823, 675376242, 286796658, 257365602, 464066474,
  495973147, 290956237, 415975178, 230769951, 429135491, 622951785, 420080723,
  145497213, 243545227, 404602647, 916788068, 341939327, 644388781, 900919332,
  903266519, 495499708, 155354851, 382350369, 290797802, 419168628, 937832458,
  842174144, 469434737, 933569873, 889500631, 340506295, 197087356, 984574899,
  828233392, 233933003, 777784901, 854132267, 927419851, 248279712, 414522544,
  465359684, 221935057, 814032530, 348108055, 470621085, 552734961, 257600139,
    .......
];


module.exports = arrayNumber;

Ao todo a array possui mil números randomicos, gostaria de uma sugestão do porquê não funciona.

1 resposta
solução!

Olá, Lucas! Tudo bem?

É importante notar que o Merge Sort é um algoritmo recursivo, ou seja, ele chama a si mesmo para ordenar subarrays até que a lista esteja completamente ordenada.

No seu código, você está chamando a função mergeSort dentro dela mesma, o que é correto. No entanto, você não definiu uma condição de parada para a recursão. Isso pode fazer com que a função fique em um loop infinito, como você mencionou.

Para corrigir esse problema, você precisa adicionar uma condição de parada para a recursão. No caso do Merge Sort, a condição de parada é quando a lista possui apenas um elemento, pois um único elemento já é considerado ordenado.

Você pode adicionar essa condição de parada no início da função mergeSort, da seguinte forma:

function mergeSort(array) {
  if (array.length <= 1) { // Condição de parada
    return array;
  }

  // Resto do código...

}

Dessa forma, quando a lista tiver apenas um elemento, a função mergeSort irá retornar o próprio array sem fazer mais chamadas recursivas.

Espero ter ajudado e bons estudos!