Merge Sort - Fluxograma | Algoritmos com JavaScript II: aprofundando em algoritmos de ordenação e busca

Solucionado (ver solução)

Solucionado
(ver solução)

2
respostas

por Gabriel Sena

| 514.1k xp | 156 posts

A function mergeSort(array) recebe um array como parâmetro, a chamamos dentro de console.log() com o argumento 'listaLivros' que é o nosso array de objetos:

const listaLivros = [
    { titulo: 'Go', preco: 45 },
    { titulo: 'C++', preco: 35 },
    { titulo: 'Java', preco: 30 },
    { titulo: 'PHP', preco: 15 },
    { titulo: 'Elixir', preco: 50 },
    { titulo: 'Rust', preco: 22 },
    { titulo: 'Scala', preco: 40 },
    { titulo: 'Ruby', preco: 28 },
    { titulo: 'JavaScript', preco: 25 },
    { titulo: 'C#', preco: 33 },
    { titulo: 'Python', preco: 20 } 
]

Então ao passarmos este array para a função 'mergeSort(listaLivros)', ela consequentemente trabalhará com esses dados. Perceba que na 'iteração 0' ela estará trabalhando com o array inteiro, logo depois temos a condição da função recursiva, 'if (array.length > 1)' esta condição é que controlará o fluxo de dados (por isto pode ser chamada de estrutura de controle, condicional, ou em recursão, caso base da recursão). Já que na 'iteração 0' o array tem 11 elementos o bloco de instruções é executado, e nele queremos dividir este array pela metade (ou seja em duas partes), então atribuímos seu resultado em uma constante, uma para primeira metade 'parte1' e outra para segunda 'parte2'. Mas analisaremos a primeira parte:

demo1

Em Math.floor(array.length / 2) o Array sempre estará sendo divido por 2 enquanto seu tamanho ser maior que 1, e a constante 'parte1' sempre ganhará a primeira metade desta divisão. Então na 'iteração 0' o array é divido por 2, mas 11 divido por dois seria 5.5, assim o floor arredonda para baixo, ficando com 5 elementos. Na 'iteração 1' o array é dividido novamente em 5/2 que daria 2.5, e assim o floor arredonda para baixo ficando apenas 2 elementos. Na 'iteração 2' o array é dividido em 2 ficando 1, mas agora a estrutura de controle não será executada, seguindo o caminho FALSO mostrado na imagem e assim apenas retorna o array inteiro. Isto ocorre também para variável que está recebendo a segunda parte 'parte2', e são com essas partes fracionárias do array que a função ordena(parte1, parte2) está trabalhando!

É claro que a função completa tem bem mais iterações e a função ordena() realiza uma série de comparações, mas perceba que ao dividirmos a primeira parte até sobrar 1 elemento, o primeiro elemento será o do índice 0, e se dividirmos a segunda parte até um elemento, chegará ao elemento de índice 1, veja a primeira comparação de ordena() sendo realizada:

Por último perceba como os elementos que possuem um maior valor como o 'Java' vão subindo até encontrar sua posição, ou como o 'PHP' que após não haver nenhuma ocorrência de menor valor ficou na primeira posição. Finalizando com a comparação entre 'Go' e 'Scala' e adicionando 'Scala' de menor valor primeiro:

Apenas queria compartilhar estes testes que fiz para entender o algoritmo apresentado na aula, particularmente porque fiquei meio perdido, mas após ter analisado bem o comportamento do código consegui entender um pouco melhor!

2 respostas

por Gabriel Sena

| 514.1k xp | 156 posts

16/04/2022

Código para quem quiser executar e testar:

const listaLivros = require('./ex007'); // Lembre-se de trocar o módulo

/*
    Recursão: Um método em que uma função ou algoritmo chama a si uma ou 
    mais vezes até que se atinja uma condição específica.
 */
nivelIteracao = 0;
function mergeSort(array) { 

    console.log();
    console.log(`Nível de iteração: ${nivelIteracao}`);
    nivelIteracao++
    console.log(array)

    if (array.length > 1) { // Bloco de controle
        const meio = Math.floor(array.length / 2); 
        const parte1 = mergeSort(array.slice(0, meio));
        const parte2 = mergeSort(array.slice(meio, array.length));
        array = ordena(parte1, parte2);  
    }
    return array;
} 

function ordena(parte1, parte2) {
    let posicaoAtualParte1 = 0;
    let posicaoAtualParte2 = 0;
    const resultado = [];
    while (posicaoAtualParte1 < parte1.length && posicaoAtualParte2 < parte2.length) {
        let produtoAtualParte1 = parte1[posicaoAtualParte1];
        let produtoAtualParte2 = parte2[posicaoAtualParte2];
        if (produtoAtualParte1.preco < produtoAtualParte2.preco) {
            resultado.push(produtoAtualParte1);
            posicaoAtualParte1++;
        } else {
            resultado.push(produtoAtualParte2);
            posicaoAtualParte2++;
        }
        console.log()
        console.log(`Produto parte1: `, produtoAtualParte1);
        console.log(`Produto parte2: `, produtoAtualParte2);
    }
    return resultado.concat(posicaoAtualParte1 < parte1.length ?
        parte1.slice(posicaoAtualParte1) : parte2.slice(posicaoAtualParte2));
}

console.log(mergeSort(listaLivros));

solução!

por Armano Barros Alves Junior

| 1538.9k xp | 3243 posts

Alura Scuba Team Monitor Escola Semente | Fórum Ops

18/04/2023

Olá Gabriel, tudo bem com você?

Desde já peço desculpa pela demora para responder o seu tópico.

Obrigada por compartilhar sua experiência conosco! É muito importante entendermos o funcionamento dos algoritmos para podermos aplicá-los de forma eficiente em nossos projetos.

O Merge Sort é um algoritmo de ordenação muito eficiente e sua explicação pode ser um pouco complexa no início, mas com paciência e dedicação, conseguimos entender seu funcionamento. É interessante analisar cada etapa do algoritmo e entender como ele divide o array em partes menores, ordena essas partes e depois as junta novamente.

Caso durante os seus estudos você tenha dúvidas ou problemas, recorra ao fórum, estamos aqui para ajudá-lo.

Abraços e bons estudos!