Professor, muito bom o seu vídeo, mas muito bom mesmo. Muito bem explicado, a qualidade do vídeo em si é boa e do áudio também. Cara, você está fazendo um trabalho heróico no UA-cam e no Brasil.
a analogia das cartas me ajudou muito a visualizar a lógica do algoritmo! muito obrigada por disponibilizar conteúdo de qualidade sobre programação em pt-br aqui no yt
Opa mestre, eu fui aluno do infnet EAD e se tivesse tido aula com você, nesse nivel de explicação provavelmente não teria abandonado a instituição! Gostaria de dizer que os vídeos estão excelentes e você explica de forma maravilhosa. Seguindo, dando like e compartilhando já! Parabéns!!!
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.
Ótimo vídeo, muito bem explicado. A ideia do algoritmo é intuitiva vendo de uma perspectiva de árvore, mas a recursão sempre me da um nó na cabeça, kkk. Quero tentar implementar isso agora em C/C++
Cara, conteúdo extremamente bem entregue, parabéns. Não vi nenhum outro vídeo no yt, nem em outras línguas, que explique tão bem a implementação, valeu!
@@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]
Obrigada pela aulas! eu não estava conseguindo entender mesmo lendo os slides do professor e você me ajudou ❤ tbm adoro ver pessoas pretas na área (tbm sou preta)
Nossa, explicou de uma maneira mais simples que o meu professor. Eu não consegui entender muito bem o código porque não estou acostumado com Python; utilizamos Java na faculdade. Mas a explicação do algoritmo ficou bem simples mesmo.
Muito bom o vídeo. Explicação bem top .agora é só eu passar para java . Procurei a internet toda finalmente achei um vídeo que dá para entender bem .ótimo trabalho 👏👏👏
Nem começou o vídeo e já vou "sapecando" like porque sempre vem coisa boa nos vídeos desse casal gente boa e competentíssimo 👏🏻👏🏻👏🏻 Parabéns pelo canal que a cada dia vem ficando mais robusto com conteúdos de grande valor 🙏🏻🙏🏻🙏🏻 #gratidao #sucesso
Conteúdo excelente. Sempre aqui aprendendo algoritmos. Halisson, você poderia me explicar a nuance do pior e melhor caso do mergesort, além da análise da complexidade, por exemplo: O porquê do melhor caso e o porquê do pior caso? O que difere entre melhor caso e o pior caso. Questões de comparações, chamadas recursivas e dentre outras rotinas.
Como que você tem a coragem de falar uma coisa dessa??????? Cheguei aqui no seu canal PQ precisava entender o merge sort e me deparo com esse vídeo seu muito bem explicado. Aí quando vou olhar o canal para me inscrever, vejo que já tem 200 mil inscritos. A pergunta inicial foi só para chamar a atenção. Você está de parabéns e merece cada curtida nos seus vídeos!!
Fala, mestre! Bom demais suas aulas, acompanho o canal já tem bastante tempo, gosto muito da maneira como você expõe o conhecimento sobre esses assuntos. Queria saber se a playlist Estruturas de Dados e Algoritmos está ordenada, estou meio confuso para seguir os vídeos. Abraços!
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 😆
Boa tarde, tudo bem? Sou fã do seu canal, poderia me dizer se caso tenha uma ocorrência, que no meu caso seria de um array, cujo tamanho seja impar o algoritmo proposto no vídeo não iria funcionar?
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.
Olá. Conheci o canal agora por esse vídeo e vou maratonar os videos. Quero ser educador nessa area. Estou estudando programação durante a pandemia pq eu iria iniciar a faculdade de S. I. no 3 período de 2020. então tô pegando as coisas antecipadamente, conheço até vetores/matrizes/strings porem somente em c. Poderia recomendar livros de linguagem C?
@@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.
Vídeo muito bom e muito bem explicado! Preciso só de ajuda com a complexidade de tempo desse algoritmo de ordenação, conseguiria fazer uma breve explicação dando como exemplo a lista de 8 números do início do vídeo? Obrigado :D
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
boa noite Hall, mano , o cormen apresenta o merge sort pegando o tamanho dos dois arrays e tambem ele usa mais parametros, to meio confuso, ta dificil de pegar esse, eu to tentando entender no livro pra depois destrinchar esse video, o que voce acha q devo fazer?
Hallison, e nos casos em que a lista tivesse tamanho multiplo de 3? Por exemplo, 6. A lista seria dividida em duas de 3, mas como seria a divisão de cada uma dessas listas separadas de tamanho 3, em listas de tamanho 1, para em seguida, comparar cada uma dessas listas de tamanho 1 e construir novamente uma de tamanho 3?
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.
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
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
Assistido✔️ Hallison por ele ser mais eficaz a complexidade dele é O(n)? Ele passa pelos elementos da lista várias vezes mas em quantidade menor e faz comparações, mas essas varias vezes que ele calcula as comparações não fariam a complexidade dele ser maior? Estou partindo do princípio que ele só vai fazer um loop for em uma condição (já que tem vários if elif else) então seria n vezes e não n².
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.
Fala Hallison, tudo bom? Cara, eu tenho uma dúvida. Nesta segunda chamada recursiva do mergesort não deveríamos passar o parametro "meio" como sendo o valor "meio + 1" não? Já que o meio termina o mergesort anterior, devo começar do primeiro a seguir?
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".
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: ua-cam.com/video/QC8oiQnlYos/v-deo.html
to tentando escrever esse algoritmo em C, mas to preso na parte de dividir o array no meio por conta dos ponteiros, ja que pode ser numero par ou impar a quantidade de elementos, é bem mais demorado mas acho que eu abstraio melhor
@@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
Professor eu tenho uma duvida. Eu estou tentando implementar o algoritmo do Tim Sort e consegui, porem quando eu ponho um Array de 10.000 números aleatórios dá um erro na parte do Merge, até agora não sei como resolver. import random def insertion_sort(array, left=0, right=None): if right is None: right = len(array) - 1 for i in range(left + 1, right + 1): key_item = array[i] j = i - 1 while j >= left and array[j] > key_item: array[j + 1] = array[j] j -= 1 array[j + 1] = key_item return array def merge(left, right): if not left: return right if not right: return left if left[0] < right[0]: return [left[0]] + merge(left[1:], right) return [right[0]] + merge(left, right[1:]) def tim_sort(array): min_run = 32 n = len(array) for i in range(0, n, min_run): insertion_sort(array, i, min((i + min_run - 1), n - 1)) size = min_run while size < n: for start in range(0, n, size * 2): midpoint = start + size - 1 end = min((start + size * 2 - 1), (n-1)) merged_array = merge( left=array[start:midpoint + 1], right=array[midpoint + 1:end + 1] ) array[start:start + len(merged_array)] = merged_array size *= 2 return array # Gerar os numeros para um array arr = [random.randint(0, 10000) for i in range(10000)] # Imprimir o array original print("Array original:") print(arr) # Ordenar o array usando o algoritmo Tim Sort arr = tim_sort(arr) # Imprimir o array ordenado print(" Array ordenado:") print(arr)
me veio um pensamento na cabeça, se houver uma lista muito grande para o merge sort dividir em listas de 1 elemento em cada variavel, pode ocorrer o erro de estouro de pilha?
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.
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 🤙🏾
Fui assistindo e copiando o código, mas aí quando chegou na parte das listas e do import eu me perdi, pois estou fazendo no Google Colab. Isso está em outro vídeo?
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?
Professor, muito bom o seu vídeo, mas muito bom mesmo.
Muito bem explicado, a qualidade do vídeo em si é boa e do áudio também.
Cara, você está fazendo um trabalho heróico no UA-cam e no Brasil.
Muuuuuitíssimo obrigado! 🦸🏾♂️🦸🏾♀️
Bom demais!
Valeu!
a analogia das cartas me ajudou muito a visualizar a lógica do algoritmo! muito obrigada por disponibilizar conteúdo de qualidade sobre programação em pt-br aqui no yt
Opa mestre, eu fui aluno do infnet EAD e se tivesse tido aula com você, nesse nivel de explicação provavelmente não teria abandonado a instituição! Gostaria de dizer que os vídeos estão excelentes e você explica de forma maravilhosa. Seguindo, dando like e compartilhando já! Parabéns!!!
Obrigado pelo apoio, Anderson! Bons estudos!
Excelente aula! Tinha que fazer a implementação em C e consegui mesmo a aula sendo em Python. Muito obrigado
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! ❤️
Cara tu é um professor incrível q didática!!!
Obrigado!
Hallison, muito obrigado por essa aula! Finalmente consegui entender como implementar esse algoritmo.
Parabéns pela didática!
Muito obrigado! Fico feliz que esteja ajudando!
Sua série de vídeos de algoritmos tem me ajudado muito. Obrigado, @Programação Dinâmica
Que ótimo saber disso! Bons estudos!
Brabo, explicação incrível.
Valeu!
Revendo após alguns anos... conteúdo sempre muito válido.
Valeu, Pedro!
Ótimo vídeo, muito bem explicado. A ideia do algoritmo é intuitiva vendo de uma perspectiva de árvore, mas a recursão sempre me da um nó na cabeça, kkk. Quero tentar implementar isso agora em C/C++
Cara, conteúdo extremamente bem entregue, parabéns. Não vi nenhum outro vídeo no yt, nem em outras línguas, que explique tão bem a implementação, valeu!
Fico feliz com o reconhecimento :D
Sensacional!!!!
Obrigado!
Sempre o lugar mais fácil de entender os assuntos que os outros possuem dificuldade para explicar!!!
👏🏾👏🏾 valeu! Ah, ficou ótimo o seu nome com esse selo verde hein 😊
Excelente aula parabéns professor, Deus abençoe ❤
Amém 🙏🏾
você e seus vídeos foram e são exatamente o que eu estava precisando... muito obrigada!
Obrigado pelas palavras!
Muito didático. Me inscrevi, muito obrigado!
Valeu, seja bem-vindo!
Excelente vídeo
Muito obrigado!
Muito didático ! Parabéns! 🙌
Muito obrigado 😃
Parabéns! Achei que não iria conseguir encontrar alguém que conseguisse explicar esse algoritmo de forma simples e com uma boa didática.
Obrigado! Bons estudos ✌🏾
Obrigado Hallison! O seu material tem sido uma fonte fantástica para meu aprendizado.
Fico feliz em saber :)
Muito bem. Que aula sensacional!
Valeu, bons estudos!
Aula é top de mais to gostando mais que minhas aulas faculdade.... didática é incrível
Obrigado! Fico feliz que esteja gostando :)
Aula incrível!
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]
Explicação clara e eficiente capaz de tornar um assunto complexo (no meu caso) em algo menos obscuro. Obrigado pelo excelente trabalho.
Valeu! 🙌🏾
excelente aula!
Muito obrigado!
Explicação fácil e concisa. Ja ganhou um assinante
Bem vindo! 🙂
cara maravilhoso a aula simplificou na minha cabeça obrigado
De nada!
Quebra tudo! Bem bolado Professor.
Valeu!
Obrigado prof
Valeu!
Muito bom mesmo! Obrigado!
De nada! 😉
Muito bom o vídeo, ótima explicação!
Excelentes vídeos.... parabéns
Valeu! Bons estudos 🙌🏾
Muito bom e didático. Muito obrigado pelo vídeo.
De nada!
Show demais viu, didática maravilhosa.
Muito obrigado, bons estudos!
Gosto muito da sua metodologia. Nunca mude, por favor 😁
Obrigado!
Obrigado caro. ótimo vídeo.
Obrigado! 🙂
Excelente aula.
Obrigado!
Valeu cara, me ajudou muito
Fico feliz em saber! Sucesso!
Muito bom,, áudio,,,, explicação,,,,, excelente,, parabéns,,,,,,,,,
Obrigado!
obrigado suas explicações estao me ajudando em um trabalho pra faculdade,cê é 10
Valeu 🙌🏾
Conteúdo de altíssima qualidade!!
Muito obrigado!
cara muito bom o seu vídeo sua explicação é excelente, tornou um assunto tão difícil em algo extremamente simples, parabéns, amei aula
Muito obrigado! 😊
Professor muito bom!
Pedro carai kkkkkkkkkkkkkkkkkkkkk
@@carlosfrederico7821 😂😂😂
Obrigado 😃, bons estudos!
Sensacional. Tava com dificuldade em entender esse algoritmo. Valeu, galera!
\o/
Esse canal me ajuda muito, valeu
🤩🤩
Estou começando a entender este algoritmo, muito obrigado. Sou auto-didata e estou tentando aprender esse algoritmos.
Show, Lucas, bom saber! Bons estudos!
Boa noite Halisson!!
obrigado pelo conteúdo. Já temos o video de analise de complexidade do MergeSort e QuickSort ?
Muito boa a explicação, obrigado. Me ajudou bastante.
Valeu! 😊
Vcs salvam demais, MUITO OBRIGADO!!
Cara voce é muito bom sz
Muito obrigado! #tmj
Cara, excelente. Parabéns. Abraço.
Valeu! 😊
Muito bom o vídeo, parabéns pela explicação
Explicação como sempre, boa demais!!
Obrigado!
Obrigada pela aulas! eu não estava conseguindo entender mesmo lendo os slides do professor e você me ajudou ❤ tbm adoro ver pessoas pretas na área (tbm sou preta)
✊🏾 🙌🏾 é nós por nós!
Parabéns pelo conteúdo! Vc é muito bom!
Muito obrigado!
Muito bom o conteúdo! Me ajudou muito com um trabalho em C !
Show, bons estudos!
Tu e fera
Obrigado!
Nossa, explicou de uma maneira mais simples que o meu professor. Eu não consegui entender muito bem o código porque não estou acostumado com Python; utilizamos Java na faculdade. Mas a explicação do algoritmo ficou bem simples mesmo.
Preciso desenvolver uma ordenação aqui hoje. Passei pra relembrar que ja nao fazia mais ideia de como implementar. KKKKKK bem explicado parabéns.
😁🙌🏾
Vídeo fantástico😍, muito bem explicado e me ajudou muito. Obrigado!
😊🙌🏾
Muito bom o vídeo. Explicação bem top .agora é só eu passar para java . Procurei a internet toda finalmente achei um vídeo que dá para entender bem .ótimo trabalho 👏👏👏
muito bom!
Obrigado!
Muito bom o vídeo amigo. Me ajudou bastante.
Que ótimo! Fico feliz 😁
Nem começou o vídeo e já vou "sapecando" like porque sempre vem coisa boa nos vídeos desse casal gente boa e competentíssimo 👏🏻👏🏻👏🏻 Parabéns pelo canal que a cada dia vem ficando mais robusto com conteúdos de grande valor 🙏🏻🙏🏻🙏🏻 #gratidao #sucesso
Seus vídeos são ótimos, parabéns!!!
Obrigado!
Conteúdo excelente. Sempre aqui aprendendo algoritmos. Halisson, você poderia me explicar a nuance do pior e melhor caso do mergesort, além da análise da complexidade, por exemplo: O porquê do melhor caso e o porquê do pior caso? O que difere entre melhor caso e o pior caso. Questões de comparações, chamadas recursivas e dentre outras rotinas.
Como que você tem a coragem de falar uma coisa dessa???????
Cheguei aqui no seu canal PQ precisava entender o merge sort e me deparo com esse vídeo seu muito bem explicado.
Aí quando vou olhar o canal para me inscrever, vejo que já tem 200 mil inscritos.
A pergunta inicial foi só para chamar a atenção. Você está de parabéns e merece cada curtida nos seus vídeos!!
Obrigado, seja bem-vindo!
Excelente! Super didático! Inscrita!
Fala, mestre!
Bom demais suas aulas, acompanho o canal já tem bastante tempo, gosto muito da maneira como você expõe o conhecimento sobre esses assuntos.
Queria saber se a playlist Estruturas de Dados e Algoritmos está ordenada, estou meio confuso para seguir os vídeos.
Abraços!
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
Sou seu fan
genioooo
Quem dera…
Ajudou d+, estava num sufoco aqui.
Sucesso!
8:30 , kk justamente o que eu tava pensando.
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 😆
Boa tarde, tudo bem? Sou fã do seu canal, poderia me dizer se caso tenha uma ocorrência, que no meu caso seria de um array, cujo tamanho seja impar o algoritmo proposto no vídeo não iria funcionar?
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
Conheci agora e to doido pra ser membro do canal 🤗
🥰🥰
Vc pode fazer um vídeo sobre o quicksort?
Sim! Quinta ou sexta sai ;)
@Felipe Santos, ficou pronto agora (quase meia-noite 😱)! Por estar tarde, agendaremos para amanhã, fique ligado ;)
As suas explicações me salvaram!
🙌🏾🙌🏾 bons estudos! :)
Olá. Conheci o canal agora por esse vídeo e vou maratonar os videos. Quero ser educador nessa area. Estou estudando programação durante a pandemia pq eu iria iniciar a faculdade de S. I. no 3 período de 2020. então tô pegando as coisas antecipadamente, conheço até vetores/matrizes/strings porem somente em c. Poderia recomendar livros de linguagem C?
Olá, seja bem vindo! Dá uma olhada em “Linguagem C” de Luís Damas
Qual é o melhor algoritmo de ordenação na opinião de vocês? E por quê?
O vídeo ficou show de bola!
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.
Vídeo muito bom e muito bem explicado! Preciso só de ajuda com a complexidade de tempo desse algoritmo de ordenação, conseguiria fazer uma breve explicação dando como exemplo a lista de 8 números do início do vídeo? Obrigado :D
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
boa noite Hall, mano , o cormen apresenta o merge sort pegando o tamanho dos dois arrays e tambem ele usa mais parametros, to meio confuso, ta dificil de pegar esse, eu to tentando entender no livro pra depois destrinchar esse video, o que voce acha q devo fazer?
Hallison, e nos casos em que a lista tivesse tamanho multiplo de 3? Por exemplo, 6. A lista seria dividida em duas de 3, mas como seria a divisão de cada uma dessas listas separadas de tamanho 3, em listas de tamanho 1, para em seguida, comparar cada uma dessas listas de tamanho 1 e construir novamente uma de tamanho 3?
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.
Hallison, parabéns pelo video.
Tenho uma duvida fora do contexto do video. Para data science, tu achar melhor Python ou R?
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!!!
oi Professor, uma duvida: porque não pode usar len(lista) como parametro no minuto 18:05 ?
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
Assistido✔️
Hallison por ele ser mais eficaz a complexidade dele é O(n)? Ele passa pelos elementos da lista várias vezes mas em quantidade menor e faz comparações, mas essas varias vezes que ele calcula as comparações não fariam a complexidade dele ser maior? Estou partindo do princípio que ele só vai fazer um loop for em uma condição (já que tem vários if elif else) então seria n vezes e não n².
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.
Oii professor tudo bem?Nunca é tarde demais para aprender kkkkk, a variável k seria o que exatamente?
Pelo oq eu entendi ela serve para armazenar a lista original temporariamente
@@CosmosCSGO ataaa, muito obrigada
Merge sort e buble sort da pra usar no java?
Fala Hallison, tudo bom?
Cara, eu tenho uma dúvida. Nesta segunda chamada recursiva do mergesort não deveríamos passar o parametro "meio" como sendo o valor "meio + 1" não? Já que o meio termina o mergesort anterior, devo começar do primeiro a seguir?
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
Como eu faria o merge retornando um int com o numero de comparações na linguagem C? to quebrando a cabeça nisso tem 1 dia já...
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: ua-cam.com/video/QC8oiQnlYos/v-deo.html
to tentando escrever esse algoritmo em C, mas to preso na parte de dividir o array no meio por conta dos ponteiros, ja que pode ser numero par ou impar a quantidade de elementos, é bem mais demorado mas acho que eu abstraio melhor
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
Professor eu tenho uma duvida. Eu estou tentando implementar o algoritmo do Tim Sort e consegui, porem quando eu ponho um Array de 10.000 números aleatórios dá um erro na parte do Merge, até agora não sei como resolver.
import random
def insertion_sort(array, left=0, right=None):
if right is None:
right = len(array) - 1
for i in range(left + 1, right + 1):
key_item = array[i]
j = i - 1
while j >= left and array[j] > key_item:
array[j + 1] = array[j]
j -= 1
array[j + 1] = key_item
return array
def merge(left, right):
if not left:
return right
if not right:
return left
if left[0] < right[0]:
return [left[0]] + merge(left[1:], right)
return [right[0]] + merge(left, right[1:])
def tim_sort(array):
min_run = 32
n = len(array)
for i in range(0, n, min_run):
insertion_sort(array, i, min((i + min_run - 1), n - 1))
size = min_run
while size < n:
for start in range(0, n, size * 2):
midpoint = start + size - 1
end = min((start + size * 2 - 1), (n-1))
merged_array = merge(
left=array[start:midpoint + 1],
right=array[midpoint + 1:end + 1]
)
array[start:start + len(merged_array)] = merged_array
size *= 2
return array
# Gerar os numeros para um array
arr = [random.randint(0, 10000) for i in range(10000)]
# Imprimir o array original
print("Array original:")
print(arr)
# Ordenar o array usando o algoritmo Tim Sort
arr = tim_sort(arr)
# Imprimir o array ordenado
print("
Array ordenado:")
print(arr)
Como seria o merge pra ordenar um vetor de strings?
Não muda nada.
no meu codigo a lista é retornada vazia
me veio um pensamento na cabeça, se houver uma lista muito grande para o merge sort dividir em listas de 1 elemento em cada variavel, pode ocorrer o erro de estouro de pilha?
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.
A lógica do Merge Sort é a mesma em qualquer linguagem? Python, java etc?
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.
Eu fiz exatamente igual ao código do vídeo, mas quando coloco para ordenar só retorna None. O que será?
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. 🥰
🙌🏾
Fui assistindo e copiando o código, mas aí quando chegou na parte das listas e do import eu me perdi, pois estou fazendo no Google Colab. Isso está em outro vídeo?
Tá distribuído em vários vídeos, mas o código completo fica aqui: github.com/python-cafe/algorithms/tree/master/sorting
Olá vc teria essa implementação em C?
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?
Onde encontro o código em C?
O código é *bem fácil* de encontrar na internet, mas você vai aprender muito mais se implementar por conta própria.