Podem até falar de escolher outro número na array por questão de ordenação, mas NINGUÉM consegue explicar essa alternativa corretamente. O cara simplesmente explicou do jeito prático e mais correto; o que depois de 10 vídeos no UA-cam, já pensava não existir mais. Só parabéns, irmão. Vídeo de 4 anos, dando a luz na minha cabeça ❤ #paz
Bacana a explicação. Apenas uma observação que acredito ser importante: selecionar o pivô como o último elemento leva a um número de operações quadrático quando a lista inicial está perto de estar já ordenada. O ideal é pegar o elemento do meio (pode simplesmente trocar de posição com o último antes de iniciar o algoritmo de partição) ou, melhor ainda, uma posição aleatória, em que a probabilidade de ter um comportamento lento será desprezível.
O cara é monstro da didática, tava uma hora olhando pro *código* de um quicksort e não conseguia replicar a implementação, vi só a parte teórica e saiu de primeira, não tem como, esse cara é bom d+.
Show! Fico feliz em ter ajudado. Particularmente, esse foi o algoritmo de ordenação que eu mais tive dificuldade de aprender quando estava na graduação.
Hallison, você poderia caso possível, completar essa mini série de videos de estrutura de dados e trazer outros algoritmos mais "tradicionais " de estrutura de dados visto que o canal já possuí vários algoritmos interessantes sobre o tema.seria legal..
Sim, é possível...se eu sobreviver ao que preciso fazer em novembro 🏃🏾♂️vou retomar essas duas séries em dezembro :) Agradeço o apoio. Esses comentários ajudam a dar noção do que priorizar 😊
Tive que escrever o código em um monitor e colocar esse vídeo no outro monitor e ficar encarando os dois durante quase 2 horas pra poder realmente entender como tudo funciona kkkkkkkk fazia tempo que eu não quebrava tanta cabeça pra entender algo mais complexo kk, mas a satisfação no final compensa
Cá estou assintindo mais uma vez seus vídeos. Parabéns!! Se puder comentar, queria entender o motivo de ser menos um em 11:05 . Tamanho da lista menos um? O que significa isso? É uma dúvida que eu carrego toda vez que vejo algo sobre algoritmo
É porque o primeiro item de uma lista começa na posição 0 ao invés da posição 1, logo o ultimo elemento dela também está sempre deslocado por "menos um" por causa disso. Exemplo: A lista [0,1,2] tem tamanho 3. Se você quiser resgatar o ultimo elemento dessa lista, naturalmente pensaríamos em algo como: lista[tamanho], mas se vc fizer isso, o programa apresentará um erro alegando que 3 não é um índice válido. Agora se você fizer lista[tamanho -1], você "compensa" o deslocamento explicado anteriormente e obtém exatamente o último item da lista, que nesse caso está no índice 2
Fiz esse código antes de ver o do vídeo Acho que assim fica mais simples, mas n sei se estou ferindo alguma regra do quick sort ou a complexidade pode estar maior, já que todo exemplo que vejo por aí é na pegada do código do vídeo. ``` def quickSort(lista): if len(lista) < 2: return lista pivo = lista[-1] m, c = 0 , 0 for i in range(len(lista) - 1): if lista[i] < pivo: lista[m], lista[c] = lista[c], lista[m] m += 1 c += 1 lista[m], lista[c] = lista[c], lista[m] lista[:m] = quickSort(lista[:m]) lista[m+1:] = quickSort(lista[m+1:]) return lista ```
por curiosidade vc estudou o cormen inteiro? eu to lendo o algorithms unnlocked do cormen e sua explicação segue bem à risca a dele e me ajuda e muito a compreensão obrigado
Não…o Cormen tem muito conteúdo. Neste outro vídeo, eu conto os tópicos que acho mais importantes: ua-cam.com/video/SqBgnMgFQTU/v-deo.html Além destes, eu estudei vários outros algoritmos específicos de computação gráfica, geometria computacional etc (alguns estão no Cormen).
Nesse tipo de algoritmo, você sempre quer que as divisões sejam o mais igualitárias possível, metade/metade (como no mergesort, busca binária etc). Se você conseguir um pivô que seja a mediana (não é média!) dos demais valores, vai ter essa propriedade a baixo custo. Por outro lado, se o pivô for o maior valor ou o menor dentre os que restam, será mais custoso fazer as trocas para ter metade de cada lado. Em uma lista que não tem nenhuma propriedade particular, você não tem como saber onde está a mediana, mas pode tentar escolher 3 valores e selecionar o pivô como o valor do meio dentre eles - nesse caso, a posição do pivô muda a cada repetição. Iteração tem um custo menor do que recursão, então se você reescrever o algoritmo na forma iterativa, vai ter um ganho de desempenho. Para tamanhos pequenos de listas, o custo das "manobras" do quicksort não compensa, então você pode optar por usar um "insertion sort" nas etapas finais do quicksort, quando detectar que a lista tem, por exemplo, 8 elementos. Repare, no entanto, que todas essas modificações geram pequenos ganhos de desempenho, sem mudar a complexidade do algoritmo. Se você quiser ter grandes ganhos de desempenho, pode fazer uma implementação paralelizada para rodar em vários núcleos. 👨🏾💻👩🏾💻
Fala Hallyson! Mais uma vez parabéns pelo canal. Sabe dizer se saiu o vídeo de análise de complexidade do quicksort e do merge sort q vc citou nos vídeos?
Hallison, se eu declarar dois ponteiros no meu array, um sendo left = start e outro como right = end-1 (um elemento antes do pivot), e for caminhando com o left da esquerda para a direita, e com o right da direita para a esquerda, eu consigo reduzir passos do algoritmo? Ou acaba dando na mesma? Ainda não estou 100% em análise de complexidade. Abraços.
@@pgdinamica, claro! Na hora de particionar, você tem um único ponteiro no início do vetor, que vai caminhando da esquerda para a dieita (i += 1). E se tivesse algo assim: ```Python left, right = start, end -1 #pitvot é o último elemento while right > left: if lista[left] lista[end]: right -= 1 else: lista[left], lista[right] = lista[right], lista[left] if lista[left] > lista[end]: lista[left], lista[end] = lista[end], lista[left] return left else: return end ``` Assim teria dois ponteiros caminhando em direção ao outro, um começando da parte direita e outro na parte esquerda.
Eu tenho uma dúvida. Quando eu vou testar a função ela não estava ordenando, então eu coloquei o return no final. Como você faz pra funcionar sem o return?
As funções “quicksort” e “partition” acessam o mesmo espaço de memória da variável “lista”; desta forma, a ordenação acontece na lista original e, por isso, não há necessidade de retornar uma nova lista. O comportamento pode variar um pouco a depender a linguagem de programação que você esteja usando. Em Python, a passagem de argumentos é por cópia, mas toda variável é uma referência, então a “lista” do programa, a “lista” dentro do quicksort e a “lista” dentro de partition são variáveis diferentes, mas todas elas são formas de acessar o mesmo endereço de memória. Pra funcionar assim numa linguagem como C ou C++, seria preciso passar uma variável do tipo ponteiro ou uma referência ou, ainda, forçar a passagem de parâmetros por referência.
Eu estou estudando sobre esse algoritmo e achei essa implementação: ua-cam.com/video/kFeXwkgnQ9U/v-deo.html Achei ela mais fácil de entender porém talvez seja menos eficiente.Alguém poderia me dizer quais as vantagens e desvantagens das duas implementações?
Podem até falar de escolher outro número na array por questão de ordenação, mas NINGUÉM consegue explicar essa alternativa corretamente.
O cara simplesmente explicou do jeito prático e mais correto; o que depois de 10 vídeos no UA-cam, já pensava não existir mais.
Só parabéns, irmão. Vídeo de 4 anos, dando a luz na minha cabeça ❤
#paz
Muito obrigado! Bons estudos 🙌🏾
a didatica do cara é tao boa que me fez implementar o quick sort de primeira, bom demais!!
Obrigado! Bons estudos!
Esse vídeo saiu no momento que eu mais preciso KKK. Obrigado, programação dinâmica!
De nada! :D
cara, queria que desse pra favoritar seu canal como primeiro resultado pra qualquer pesquisa de algoritmos
obrigado pelo conteúdo, muito bem explicado
esse foi o primeiro algoritmo de sort q eu vi e consegui entender até que fácil de primeira
Que ótimo! Bons estudos!
Algoritmo complexo, mas bem explicado. Parabéns pelo vídeo
Obrigado! :D
Bacana a explicação. Apenas uma observação que acredito ser importante: selecionar o pivô como o último elemento leva a um número de operações quadrático quando a lista inicial está perto de estar já ordenada. O ideal é pegar o elemento do meio (pode simplesmente trocar de posição com o último antes de iniciar o algoritmo de partição) ou, melhor ainda, uma posição aleatória, em que a probabilidade de ter um comportamento lento será desprezível.
O cara é monstro da didática, tava uma hora olhando pro *código* de um quicksort e não conseguia replicar a implementação, vi só a parte teórica e saiu de primeira, não tem como, esse cara é bom d+.
Hahaha, muito obrigado! Bons estudos 🙌🏾
Didática excelente, meu amigo. Obrigado!
valeu!
Nossa, vídeo maravilhoso, muito bem explicado! Melhor vídeo que vi explicando o algoritmo. Obrigada!
😉
Incrível, vídeo perfeitooo
Obrigado!
vídeo muito bem explicado, não entendi nada quando minha professora explicou, obg pelo video.
Muito bom, parabéns
Obrigado!
Consegui implementar em C graças a esse video, valeu mesmo
Sinal de que entendeu bem a ideia por trás do algoritmo ;) parabéns!
Muito obrigada por essa explicação! Já tinha lido/assistido algumas outras mas foi só com a tua que entendi certinho 🙌
Fico feliz em saber! Bons estudos!
Esse vídeo me ajudou muito, tudo muito bem explicado!!!! obrigada
Excelente! Super didático!
Obrigado!
esse canal precisa ser divulgado ! sensacional.
Muito obrigado, ajuda muito compartilhar! 🙌🏾
Cara .. muito obrigado...estava muito perdido e vc me deu uma luz no fim do túnel.. 🙏🏽🙏🏽🙏🏽
Muito bem explicado. Ajudou muito.
Valeu!
Cara nunca tinha entendido esse algoritmo, da forma que vc explicou ficou muito claro e simples brigadão msm
Show! Fico feliz em ter ajudado. Particularmente, esse foi o algoritmo de ordenação que eu mais tive dificuldade de aprender quando estava na graduação.
melhor explicação de todas, obrigado
Valeu!
que video incrível, parabéns
Valeu!
Cara, ganhou meu like só pela referência ao Iron Maiden hahah. Incrível aula, cara.
Valeu 🤘🏾
Excelente material! Estou curtindo muito revisar essas estruturas de dados pelo seu canal. Parabéns pela qualidade. Abraço!
Muito obrigado!
salvou demais, só passando pra agradecer por sua existência. Obrigada pela didática incrível!
Valeu, Tainá! 🙌🏾
Cara, tu é sensacional kkkk
Valeu! 🙂
Salvou muito!!!
😁🙌🏾
Adorei este vídeo e sinceramente é muito massa a forma como você explica, parabéns 💯👏
Super obrigada :)
Super de nada ;)
Sério, seus vídeos de #ordenação me cativaram, amei o canal, você explica muito bem 😎
Muito obrigado!
Também estava precisando desse conteúdo. Sempre material de primeira, obrigado!
Valeu! Bons estudos!
Assistido ✔️
🚀
Hallison, você poderia caso possível, completar essa mini série de videos de estrutura de dados e trazer outros algoritmos mais "tradicionais " de estrutura de dados visto que o canal já possuí vários algoritmos interessantes sobre o tema.seria legal..
Sim, é possível...se eu sobreviver ao que preciso fazer em novembro 🏃🏾♂️vou retomar essas duas séries em dezembro :)
Agradeço o apoio. Esses comentários ajudam a dar noção do que priorizar 😊
Muito bom o seu vídeo!! Obrigada pela ajuda, vey
De nada 😉
Tive que escrever o código em um monitor e colocar esse vídeo no outro monitor e ficar encarando os dois durante quase 2 horas pra poder realmente entender como tudo funciona kkkkkkkk fazia tempo que eu não quebrava tanta cabeça pra entender algo mais complexo kk, mas a satisfação no final compensa
Com determinação, a gente sobe de nível ⬆️ 👏🏾👏🏾👏🏾👏🏾
Obrigada. Muito bom!
Excelente vídeo! Ajudou muito!
Cá estou assintindo mais uma vez seus vídeos. Parabéns!! Se puder comentar, queria entender o motivo de ser menos um em 11:05 . Tamanho da lista menos um? O que significa isso? É uma dúvida que eu carrego toda vez que vejo algo sobre algoritmo
É porque o primeiro item de uma lista começa na posição 0 ao invés da posição 1, logo o ultimo elemento dela também está sempre deslocado por "menos um" por causa disso.
Exemplo:
A lista [0,1,2] tem tamanho 3.
Se você quiser resgatar o ultimo elemento dessa lista, naturalmente pensaríamos em algo como: lista[tamanho], mas se vc fizer isso, o programa apresentará um erro alegando que 3 não é um índice válido.
Agora se você fizer lista[tamanho -1], você "compensa" o deslocamento explicado anteriormente e obtém exatamente o último item da lista, que nesse caso está no índice 2
Show de bola. Você explica tão bem. Seria possível você gravar um vídeo sobre grafos? Grato desde já!
Pretendo gravar sobre grafos :)
@@pgdinamica Ah eeee!!!
Muito obrigada! Me salvou pra prova hehehe
Agora é só buscar o 💯 :)
vcs sao pikas!!!
Valeu 🙌🏾
muito boa a didática, melhor que muito canal gringo
Muito obrigado! 🙌🏾😁
Sempre excelente! :)
ganhou um escrito, que video mara ! estava precisando !!
Que bom que ajudou, bons estudos!
Ótimo vídeo. Vai ter de heap sort tbm? acho ele interessante, mas um pouco chato de implementar.
Muito obrigado! Heapsort tá na fila, mas talvez só lá pra março. O foco agora está nas árvores balanceadas e seus algoritmos.
valeu pelo video
🤙🏾
Você poderia trazer alguns videos sobre grafo!
como: busca em um grafo algoritmo de diskistra .....
Fiz esse código antes de ver o do vídeo Acho que assim fica mais simples, mas n sei se estou ferindo alguma regra do quick sort ou a complexidade pode estar maior, já que todo exemplo que vejo por aí é na pegada do código do vídeo.
```
def quickSort(lista):
if len(lista) < 2:
return lista
pivo = lista[-1]
m, c = 0 , 0
for i in range(len(lista) - 1):
if lista[i] < pivo:
lista[m], lista[c] = lista[c], lista[m]
m += 1
c += 1
lista[m], lista[c] = lista[c], lista[m]
lista[:m] = quickSort(lista[:m])
lista[m+1:] = quickSort(lista[m+1:])
return lista
```
aula foda, parabéns e obrigado kkkkkk
De nada! Bons estudos 🙌🏾
em JS entrou num loop infinito, tive que alterar "p = partition(vetor,inicio, fim-1)" para corrigir
Excelente vídeo, muito bem explicado 😁.Vai ter da implementação utilizando o particionamento de Hoare também ?
Não pretendo fazer vídeo, mas quem sabe um artigo? 🤔
por curiosidade vc estudou o cormen inteiro? eu to lendo o algorithms unnlocked do cormen e sua explicação segue bem à risca a dele e me ajuda e muito a compreensão obrigado
Não…o Cormen tem muito conteúdo. Neste outro vídeo, eu conto os tópicos que acho mais importantes: ua-cam.com/video/SqBgnMgFQTU/v-deo.html
Além destes, eu estudei vários outros algoritmos específicos de computação gráfica, geometria computacional etc (alguns estão no Cormen).
O que posso fazer para melhorar o desempenho do quick sort, e como a escolha do pivô influencia no desempenho?
Nesse tipo de algoritmo, você sempre quer que as divisões sejam o mais igualitárias possível, metade/metade (como no mergesort, busca binária etc). Se você conseguir um pivô que seja a mediana (não é média!) dos demais valores, vai ter essa propriedade a baixo custo. Por outro lado, se o pivô for o maior valor ou o menor dentre os que restam, será mais custoso fazer as trocas para ter metade de cada lado. Em uma lista que não tem nenhuma propriedade particular, você não tem como saber onde está a mediana, mas pode tentar escolher 3 valores e selecionar o pivô como o valor do meio dentre eles - nesse caso, a posição do pivô muda a cada repetição.
Iteração tem um custo menor do que recursão, então se você reescrever o algoritmo na forma iterativa, vai ter um ganho de desempenho. Para tamanhos pequenos de listas, o custo das "manobras" do quicksort não compensa, então você pode optar por usar um "insertion sort" nas etapas finais do quicksort, quando detectar que a lista tem, por exemplo, 8 elementos.
Repare, no entanto, que todas essas modificações geram pequenos ganhos de desempenho, sem mudar a complexidade do algoritmo. Se você quiser ter grandes ganhos de desempenho, pode fazer uma implementação paralelizada para rodar em vários núcleos. 👨🏾💻👩🏾💻
Você tem algum vídeo sobre 3-Way Quick Sort?
Não... 😕
Fala Hallyson! Mais uma vez parabéns pelo canal.
Sabe dizer se saiu o vídeo de análise de complexidade do quicksort e do merge sort q vc citou nos vídeos?
Vish, saiu ainda não 😕
Hallison, se eu declarar dois ponteiros no meu array, um sendo left = start e outro como right = end-1 (um elemento antes do pivot), e for caminhando com o left da esquerda para a direita, e com o right da direita para a esquerda, eu consigo reduzir passos do algoritmo? Ou acaba dando na mesma? Ainda não estou 100% em análise de complexidade. Abraços.
Não entendi como você quer usar essa ideia no Quicksort, pode explicar um pouco mais?
@@pgdinamica, claro!
Na hora de particionar, você tem um único ponteiro no início do vetor, que vai caminhando da esquerda para a dieita (i += 1). E se tivesse algo assim:
```Python
left, right = start, end -1 #pitvot é o último elemento
while right > left:
if lista[left] lista[end]:
right -= 1
else:
lista[left], lista[right] = lista[right], lista[left]
if lista[left] > lista[end]:
lista[left], lista[end] = lista[end], lista[left]
return left
else:
return end
```
Assim teria dois ponteiros caminhando em direção ao outro, um começando da parte direita e outro na parte esquerda.
Top
Valeu!
tem o comb sort que é um bom e rápido algoritmo de ordenação que é uma melhora do buble sort
Anotado! ✍🏾
Eu tenho uma dúvida.
Quando eu vou testar a função ela não estava ordenando, então eu coloquei o return no final. Como você faz pra funcionar sem o return?
As funções “quicksort” e “partition” acessam o mesmo espaço de memória da variável “lista”; desta forma, a ordenação acontece na lista original e, por isso, não há necessidade de retornar uma nova lista. O comportamento pode variar um pouco a depender a linguagem de programação que você esteja usando. Em Python, a passagem de argumentos é por cópia, mas toda variável é uma referência, então a “lista” do programa, a “lista” dentro do quicksort e a “lista” dentro de partition são variáveis diferentes, mas todas elas são formas de acessar o mesmo endereço de memória. Pra funcionar assim numa linguagem como C ou C++, seria preciso passar uma variável do tipo ponteiro ou uma referência ou, ainda, forçar a passagem de parâmetros por referência.
@@pgdinamica Entendi!!
Ótima resposta, muito obrigado 🙏🏻
Por que o Quicksort é melhor que os outros algoritmos de ordenação??
pelo tempo de execução da recursividade ser menor que o tempo de execução das chamadas por exemplo do bubble
Mio que tem no YT
Haha, valeu!
Radix Sort?
🤔 é uma possibilidade. Obrigado pela sugestão!
Eu estou estudando sobre esse algoritmo e achei essa implementação: ua-cam.com/video/kFeXwkgnQ9U/v-deo.html
Achei ela mais fácil de entender porém talvez seja menos eficiente.Alguém poderia me dizer quais as vantagens e desvantagens das duas implementações?
tendi foi nada :/
O inventor desse alg. deveria estar preso, mas os gringos se acham tanto, que divulgam seus próprios nomes associados a porcarias como esta.
? 🫤
Você complicou mais do que explicou... a escolha do pivô foi a pior pra explicar esse algoritmo...
Não concordamos, mas valeu pelo feedback 😉