Solucionado (ver solução)
Solucionado
(ver solução)
2
respostas

Entendimento do merge sort

Pessoal, estou com SÉRIOS problemas em entender esse merge sorte (estou travado nisso tentando entender uns 5 dias kkk), eu quero entender bem como tudo esta funcionando no codigo pois da forma que esta na minha cabeça agora, sozinho eu nao iria conseguir montar ele, estou com duvida na parte do ^ return array; ^, enquanto está desorganizado o if esta funcionando e partindo os arrays no meio e organizando certo ? pq depois que eles começam a se juntar e ficar organizado os arrays o if não continua funcionando e partindo os arrays ? na minha cabeça deveria entrar na condição if de novo, mesmo que organizado pois as vezes o array tem mais que um elemento

const listaLivros = require("./array2");

function mergeSort(array, nivel = 0){

if(array.length > 1){
    console.log("")
    console.log(`array entrando em merge sorte `)
    console.log("")
    console.log(`nivel = ${nivel}`)
    console.log("")
    console.log(array)
    console.log("")
    const meioArray = Math.floor(array.length/2);
    const lista1 = mergeSort(array.slice(0,meioArray), nivel + 1);
    const lista2 = mergeSort(array.slice(meioArray, array.length), nivel + 1);
    array = ordena(lista1, lista2)
}
return array; 

}

function ordena(lista1, lista2){ console.log('lista 1 -') console.log("") console.log(lista1) console.log("") console.log('lista 2 -') console.log("") console.log(lista2) console.log("") let posLista1 = 0 let posLista2 = 0 const resultado = [];

while(posLista1 < lista1.length && posLista2 < lista2.length){

    let produtoAtualLista1 = lista1[posLista1]
    let produtoAtualLista2 = lista2[posLista2]

    if(produtoAtualLista1.preco < produtoAtualLista2.preco){

        resultado.push(produtoAtualLista1);
        console.log("produto 1 passou na frente")
        posLista1++
    }else{
        resultado.push(produtoAtualLista2);
        console.log("produto 2 passou na frente")
        posLista2++
    }

}
let resultado2 = resultado.concat(posLista1 < lista1.length ? (lista1.slice(posLista1)): (lista2.slice(posLista2)));
console.log("")
console.log("saindo de ordena - ")
console.log("")
console.log(resultado2)
console.log("")

return resultado2

}

console.log(mergeSort(listaLivros));

2 respostas
solução!

Oi Nicolas, tudo bem?

Entendo que o conceito de Merge Sort pode ser um pouco desafiador no início, mas vou tentar esclarecer suas dúvidas.

O Merge Sort é um algoritmo de ordenação que utiliza a estratégia de dividir para conquistar. Ele divide o array em duas metades, ordena essas metades e depois as combina. A parte da combinação é feita pela função ordena.

Quando você pergunta por que o if não continua partindo os arrays mesmo depois de eles começarem a se juntar, a resposta está na lógica do algoritmo. O if na função mergeSort serve para dividir o array em partes menores até que cada parte tenha apenas um elemento. Quando o array tem apenas um elemento, a função retorna esse elemento. Isso é a base da recursão no Merge Sort.

Depois que todos os arrays têm apenas um elemento, o processo de "juntar" começa. A função ordena é chamada para combinar os arrays de um elemento em arrays maiores e ordenados. Nesse ponto, o if na função mergeSort não é mais verdadeiro, porque os arrays que estão sendo combinados têm mais de um elemento. Portanto, a função mergeSort não divide mais os arrays; em vez disso, ela retorna o array combinado e ordenado pela função ordena.

Vamos ver um exemplo para esclarecer:

Suponha que temos um array [4, 3, 2, 1]. O Merge Sort funciona assim:

  1. Divide o array em duas metades: [4, 3] e [2, 1].
  2. Divide cada metade em duas até que cada array tenha apenas um elemento: [4], [3], [2], [1].
  3. Começa a combinar os arrays de um elemento em arrays maiores e ordenados: [3, 4], [1, 2].
  4. Combina os arrays maiores até obter o array original, mas ordenado: [1, 2, 3, 4].

Espero que isso ajude a esclarecer o funcionamento do Merge Sort. A chave é entender que o algoritmo primeiro divide o array até que cada parte tenha apenas um elemento e depois combina essas partes em um array maior e ordenado.

Um abraço e bons estudos.

Lorena, MUITO obrigado! de verdade, me fez girar a chavinha e entender, agora ja posso continuar, estava travado nisso. :)))