MERGE SORT | Algoritmos #7 

Muuuuuitíssimo obrigado! 🦸🏾‍♂️🦸🏾‍♀️

De nada! 😉

Valeu!

Obrigado!

Valeu!

De nada!

Valeu, seja bem-vindo!

Fico feliz em saber! Sucesso!

🙌🏾🙌🏾 bons estudos! :)

Obrigado!

🤩🤩

Obrigado pelas palavras!

Muito obrigado!

De nada!

Obrigado!

Muito obrigado!

😊🙌🏾

Obrigado!

Que ótimo saber disso! Bons estudos!

Obrigado! 🙂

Muito obrigado!

Obrigado!

Valeu, bons estudos!

Fico feliz em saber :)

Valeu! 😊

\o/

Obrigado!

Muito obrigado!

Que ótimo! Fico feliz 😁

Valeu! 😊

Valeu! Bons estudos 🙌🏾

Quem dera…

Muito obrigado 😃

Valeu!

Obrigado pelo apoio, Anderson! Bons estudos!

Fico feliz com o reconhecimento :D

Valeu!

Muito obrigado! 😊

Muito obrigado! Fico feliz que esteja ajudando!

Muito obrigado, bons estudos!

Obrigado!

Muito obrigado! #tmj

Obrigado!

Bem vindo! 🙂

Parabéns! Sinal de que entendeu mesmo a essência do algoritmo. A ideia, o conceito, tem que ser independente de linguagem :) Quando eu fiz o curso na faculdade, também foi em C.

Estou fazendo exatamente a mesma coisa e tá dando super certo! Canal excelente! ❤️

Show, bons estudos!

Amém 🙏🏾

Obrigado!

Valeu! 🙌🏾

Muito obrigado!

@@pgdinamica eu fiz um passo a passo para debugar o algoritmo no Jupyter e conseguir entender melhor a lógica, vou compartilhar aqui caso ajude alguém haha def mergesort(lista, inicio=0, fim=None): if fim is None: fim = len(lista) if (fim - inicio > 1): meio = (fim + inicio) // 2 print(f"Dividindo: {lista[inicio:fim]} em {lista[inicio:meio]} e {lista[meio:fim]}") mergesort(lista, inicio, meio) mergesort(lista, meio, fim) merge(lista, inicio, meio, fim) def merge(lista, inicio, meio, fim): left = lista[inicio:meio] right = lista[meio:fim] top_left, top_right = 0, 0 print(f"Merging: {left} e {right}") for k in range(inicio, fim): if top_left >= len(left): lista[k] = right[top_right] top_right = top_right + 1 elif top_right >= len(right): lista[k] = left[top_left] top_left = top_left + 1 elif left[top_left] < right[top_right]: lista[k] = left[top_left] top_left = top_left + 1 else: lista[k] = right[top_right] top_right = top_right + 1 print(f"Resultado do merge: {lista[inicio:fim]}") # Lista a ser ordenada lista_ = [4, 7, 2, 6, 4, 1, 8, 3] # Imprimindo a lista antes da ordenação print("Lista antes da ordenação:", lista_) # Chamando a função mergesort mergesort(lista_) # Imprimindo a lista após a ordenação print("Lista após a ordenação:", lista_) A saída no console do Jupyter ficou assim: Lista antes da ordenação: [4, 7, 2, 6, 4, 1, 8, 3] Dividindo: [4, 7, 2, 6, 4, 1, 8, 3] em [4, 7, 2, 6] e [4, 1, 8, 3] Dividindo: [4, 7, 2, 6] em [4, 7] e [2, 6] Dividindo: [4, 7] em [4] e [7] Merging: [4] e [7] Resultado do merge: [4, 7] Dividindo: [2, 6] em [2] e [6] Merging: [2] e [6] Resultado do merge: [2, 6] Merging: [4, 7] e [2, 6] Resultado do merge: [2, 4, 6, 7] Dividindo: [4, 1, 8, 3] em [4, 1] e [8, 3] Dividindo: [4, 1] em [4] e [1] Merging: [4] e [1] Resultado do merge: [1, 4] Dividindo: [8, 3] em [8] e [3] Merging: [8] e [3] Resultado do merge: [3, 8] Merging: [1, 4] e [3, 8] Resultado do merge: [1, 3, 4, 8] Merging: [2, 4, 6, 7] e [1, 3, 4, 8] Resultado do merge: [1, 2, 3, 4, 4, 6, 7, 8] Lista após a ordenação: [1, 2, 3, 4, 4, 6, 7, 8]

Pedro carai kkkkkkkkkkkkkkkkkkkkk

@@carlosfrederico7821 😂😂😂

Obrigado 😃, bons estudos!

Obrigado! Bons estudos ✌🏾

Valeu 🙌🏾

🥰🥰

👏🏾👏🏾 valeu! Ah, ficou ótimo o seu nome com esse selo verde hein 😊

Show, Lucas, bom saber! Bons estudos!

Obrigado! Fico feliz que esteja gostando :)

Oi, Klysman Rezende, muito obrigado! Obrigado por chamar a atenção quanto a essa playlist. Reorganizamos ela apenas com os vídeos de "Estruturas de Dados" (tudo ordenado!). Há uma outra playlist chamada 'Projeto e Análise de Algoritmos" que contém os vídeos específicos sobre algoritmos (até o momento abordamos apenas ordenação). []s

Hahahaha, você vai ver que esse tipo de ideia se repete em muitas outras situações na computação, talvez quem pensou no Mergesort não tenha sido o primeiro 😆

😁🙌🏾

Sucesso!

complexidade do merge sort eh de nlogn, na linha i de recursão temq unir 2^i vetores ordenados de tamanho n/2^i, dai qnd dividir o vetor no meio c m sendo a quantidade de linhas, fica n/2^m=1, isolando o m da logan em cada linha, mas você tem que fazer isso n vezes, logo, a complexidade da nlogn

Olá, seja bem vindo! Dá uma olhada em “Linguagem C” de Luís Damas

Tá fazendo trabalho da faculdade? 👀

@@pgdinamica Que nada, hahaha... só pra saber a opinião de vocês mesmo. Vi alguns vídeos na internet e não consigo chegar em uma conclusão, estou entre o quick sort e o merge sort.

Sim! Quinta ou sexta sai ;)

@Felipe Santos, ficou pronto agora (quase meia-noite 😱)! Por estar tarde, agendaremos para amanhã, fique ligado ;)

Não sei se entendi a pergunta. Se a pergunta for: "Este algoritmo funciona quando o tamanho do array é ímpar?" - Sim. "Este algoritmo funciona quando há um número ímpar de ocorrências de quaisquer que sejam os elementos no array?" - Sim. Dada uma estrutura de alocação de memória sequencial (array, lista...) com elementos cuja ordem entre eles é bem definida (é sempre possível saber quem é maior/menor que quem), este algoritmo ordena os elementos da estrutura.

@@pgdinamica Entendi, obrigado

Fala, @João Victor Assis, tudo bem? A sua dúvida é bem frequente e tá totalmente no contexto do canal, apesar de não ser o assunto deste vídeo, hehe. Resolvemos escrever um artigo para respondê-la dando um pouco mais de detalhes que não caberia aqui. Confira no link: medium.com/programacaodinamica/python-ou-r-para-data-science-221aa5637122

@@pgdinamica Cara, muito obrigado. Virei mais fã ainda, só força!!!

Fala, Carlos! Nesse caso, um lado fica com apenas 1 elemento e para no próximo passo. O outro lado segue com 2 elementos e faz mais uma subdivisão. Esses 2 serão unidos de forma ordenada primeiro e, depois aquele sozinho se unirá à eles de forma ordenada.

A complexidade do Merge Sorte é O(n*log(n)). Você pode pensar no logaritmo na base 2. Pra cada uma das n posições, você vê no máximo log(n) operações, pois está dividindo por 2 sucessivamente.

Você precisa de uma variável que armazena o número de comparações realizadas durante o merge. Como o procedimento é recursivo, você pode incrementar os valores com uma estratégia parecida com a que usamos no cálculo da altura de uma árvore binária: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-QC8oiQnlYos.html

Em Python, os intervalos (range) são fechados no início (inclui) e abertos no final (exclui). Em: "for k in range(inicio, fim):", k vai até fim-1. Na primeira chamada, "meio" entra como "fim", então vamos até "meio-1". Na segunda, entra como "incio", então começamos de "meio".

@@pgdinamica excelente! Obrigado. Eu sou de javascript e java, dai não estou acostumado com esses detalhes rs

Pq se o fizesse, a função iria considerar a variável lista de escopo local (dentro da própria função), ou seja, a variável lista que está como parâmetro, e não a lista que é passada em si

Uma opção é dividir por 2 e fazer casting do resultado pra int. Desta forma, você sempre vai arredondar pra baixo.

@@pgdinamica obrigado Hall, voce usou o cormen na sua graduação? acha um bom livro pra pessoa seguir por conta propria como eu to fazendo? to um pouco devagar mas sinto que to aprendendo de fato

Sim, muito bem observado! Neste caso, seria melhor usar um algoritmo com versão iterativa ou, ainda, fazer uma ordenação “off-line” usando a memória secundária.

Tá distribuído em vários vídeos, mas o código completo fica aqui: github.com/python-cafe/algorithms/tree/master/sorting

Fala, Luciano! A forma como o tempo de execução varia com o tamanho da entrada é a mesma, pois depende da complexidade. Contudo, o tempo de execução vai mudar. Para uma mesma entrada, em um mesmo computador, em C será mais rápido, mas será mais fácil distinguir isso com entradas maiores (milhões de dados ou mais).

Sim. É a lógica que caracteriza o algoritmo, não o código. Merge Sort foi inventado muito antes de Java, Python, JavaScript e várias outras linguagens que são populares hoje em dia.

Oi, amigo, repara que a função não tem "return", ela ordena a lista passada como entrada. Após chamar a função, exiba a lista e verifique se ela está ordenada 🤙🏾

@@pgdinamica Ah, tá! Agora entendi. Muito obrigado. Parabéns pelo canal. Os conteúdos são incríveis. 🥰

🙌🏾

Bons estudos!

O código é *bem fácil* de encontrar na internet, mas você vai aprender muito mais se implementar por conta própria.

Na função 'mergeSort' a condição 'inicio>fim' está errada.

Olá, qual dificuldade você está enfrentando para implementar em C a partir da explicação? Você entendeu a ideia do algoritmo? Se você só copiar o código, não vai aprender.

@@pgdinamica olá entendi a idéia sim , mas não sei python, é um pouco diferente, e fiquei com muita dificuldade em implementar em C, seria ótima se houvesse uma explicação passo a passo como esse do video, será que ainda vai rolar?

🥳