QUICKSORT | Algoritmos #8

[@andreattamatheus]

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 KZbin, já pensava não existir mais. Só parabéns, irmão. Vídeo de 4 anos, dando a luz na minha cabeça ❤ #paz

[@pgdinamica]

Muito obrigado! Bons estudos 🙌🏾

[@rfigueiredo]

cara, queria que desse pra favoritar seu canal como primeiro resultado pra qualquer pesquisa de algoritmos obrigado pelo conteúdo, muito bem explicado

[@dudz1978]

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.

[@guilhermesergio4861]

Esse vídeo saiu no momento que eu mais preciso KKK. Obrigado, programação dinâmica!

[@pgdinamica]

De nada! :D

[@douglasfanucchi]

a didatica do cara é tao boa que me fez implementar o quick sort de primeira, bom demais!!

[@pgdinamica]

Obrigado! Bons estudos!

[@FelipeSantos-rz1ro]

Algoritmo complexo, mas bem explicado. Parabéns pelo vídeo

[@pgdinamica]

Obrigado! :D

[@leep7562]

esse foi o primeiro algoritmo de sort q eu vi e consegui entender até que fácil de primeira

[@pgdinamica]

Que ótimo! Bons estudos!

[@julianadantas1809]

Nossa, vídeo maravilhoso, muito bem explicado! Melhor vídeo que vi explicando o algoritmo. Obrigada!

[@pgdinamica]

😉

[@victoremanoel8114]

vídeo muito bem explicado, não entendi nada quando minha professora explicou, obg pelo video.

[@fredesch3158]

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+.

[@pgdinamica]

Hahaha, muito obrigado! Bons estudos 🙌🏾

[@AndersonMarques-ik3tp]

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..

[@pgdinamica]

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 😊

[@user-fo5iv1rg6r]

Didática excelente, meu amigo. Obrigado!

[@pgdinamica]

valeu!

[@marcelafeldens2603]

Muito obrigada por essa explicação! Já tinha lido/assistido algumas outras mas foi só com a tua que entendi certinho 🙌

[@pgdinamica]

Fico feliz em saber! Bons estudos!

[@alyssandro4343]

Cara, ganhou meu like só pela referência ao Iron Maiden hahah. Incrível aula, cara.

[@pgdinamica]

Valeu 🤘🏾

[@Krawdio]

Cara .. muito obrigado...estava muito perdido e vc me deu uma luz no fim do túnel.. 🙏🏽🙏🏽🙏🏽

[@marcospaulosilvaviana3160]

Adorei este vídeo e sinceramente é muito massa a forma como você explica, parabéns 💯👏

[@rodrigomachadoluz1597]

esse canal precisa ser divulgado ! sensacional.

[@pgdinamica]

Muito obrigado, ajuda muito compartilhar! 🙌🏾

[@yasmimstephanie5763]

Esse vídeo me ajudou muito, tudo muito bem explicado!!!! obrigada

[@fcipreste1]

Também estava precisando desse conteúdo. Sempre material de primeira, obrigado!

[@pgdinamica]

Valeu! Bons estudos!

[@herbesondias791]

Excelente material! Estou curtindo muito revisar essas estruturas de dados pelo seu canal. Parabéns pela qualidade. Abraço!

[@pgdinamica]

Muito obrigado!

[@gustavobassaco1119]

Consegui implementar em C graças a esse video, valeu mesmo

[@pgdinamica]

Sinal de que entendeu bem a ideia por trás do algoritmo ;) parabéns!

[@tainasantana4562]

salvou demais, só passando pra agradecer por sua existência. Obrigada pela didática incrível!

[@pgdinamica]

Valeu, Tainá! 🙌🏾

[@XandFernandes]

Cara nunca tinha entendido esse algoritmo, da forma que vc explicou ficou muito claro e simples brigadão msm

[@pgdinamica]

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.

[@pablopolito1143]

Cara, tu é sensacional kkkk

[@pgdinamica]

Valeu! 🙂

[@lucaspaixao3659]

Sério, seus vídeos de #ordenação me cativaram, amei o canal, você explica muito bem 😎

[@pgdinamica]

Muito obrigado!

[@gabrielgmendonca]

Excelente! Super didático!

[@pgdinamica]

Obrigado!

[@carollinecarvalho287]

Incrível, vídeo perfeitooo

[@pgdinamica]

Obrigado!

[@mrkdav]

Salvou muito!!!

[@pgdinamica]

😁🙌🏾

[@ricardoriiuitikameoka5361]

Muito bem explicado. Ajudou muito.

[@pgdinamica]

Valeu!

[@JoaoODragonborn]

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 ```

[@TriateDigital]

melhor explicação de todas, obrigado

[@pgdinamica]

Valeu!

[@rodrigo9494]

que video incrível, parabéns

[@pgdinamica]

Valeu!

[@anab.9096]

Muito bom o seu vídeo!! Obrigada pela ajuda, vey

[@pgdinamica]

De nada 😉

[@marcelo.leite.pereira]

Muito bom, parabéns

[@pgdinamica]

Obrigado!

[@raniel0511]

Assistido ✔️

[@pgdinamica]

🚀

[@eduardo.chaves]

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

[@pgdinamica]

Com determinação, a gente sobe de nível ⬆️ 👏🏾👏🏾👏🏾👏🏾

[@rodrigopeddinghausen3884]

Excelente vídeo! Ajudou muito!

[@jonathankevinmendesramirez4203]

vcs sao pikas!!!

[@pgdinamica]

Valeu 🙌🏾

[@elkesamantha]

Obrigada. Muito bom!

[@priscilla9291]

Muito obrigada! Me salvou pra prova hehehe

[@pgdinamica]

Agora é só buscar o 💯 :)

[@joseferreiragomes5049]

ganhou um escrito, que video mara ! estava precisando !!

[@pgdinamica]

Que bom que ajudou, bons estudos!

[@hil449]

muito boa a didática, melhor que muito canal gringo

[@pgdinamica]

Muito obrigado! 🙌🏾😁

[@TiagoSantos-ed6zk]

Show de bola. Você explica tão bem. Seria possível você gravar um vídeo sobre grafos? Grato desde já!

[@pgdinamica]

Pretendo gravar sobre grafos :)

[@TiagoSantos-ed6zk]

@@pgdinamica Ah eeee!!!

[@gracieledeoliveira4467]

Super obrigada :)

[@pgdinamica]

Super de nada ;)

[@sezioclenernascimento5234]

Você poderia trazer alguns videos sobre grafo! como: busca em um grafo algoritmo de diskistra .....

[@kizzy_terra]

Sempre excelente! :)

[@pgdinamica]

[@josethz00]

aula foda, parabéns e obrigado kkkkkk

[@pgdinamica]

De nada! Bons estudos 🙌🏾

[@alexandredesiqueiramelojun9976]

valeu pelo video

[@pgdinamica]

🤙🏾

[@VictorLellis]

Ótimo vídeo. Vai ter de heap sort tbm? acho ele interessante, mas um pouco chato de implementar.

[@pgdinamica]

Muito obrigado! Heapsort tá na fila, mas talvez só lá pra março. O foco agora está nas árvores balanceadas e seus algoritmos.

[@petrusdemelodev]

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?

[@pgdinamica]

Vish, saiu ainda não 😕

[@fernando2852]

O que posso fazer para melhorar o desempenho do quick sort, e como a escolha do pivô influencia no desempenho?

[@pgdinamica]

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. 👨🏾‍💻👩🏾‍💻

[@marcusneiva2338]

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

[@Linkk2011]

É 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

[@josuef.c165]

Por que o Quicksort é melhor que os outros algoritmos de ordenação??

[@reynaldo_Costa]

pelo tempo de execução da recursividade ser menor que o tempo de execução das chamadas por exemplo do bubble

[@draconyxRPG]

em JS entrou num loop infinito, tive que alterar "p = partition(vetor,inicio, fim-1)" para corrigir

[@lucaspaixao3659]

Excelente vídeo, muito bem explicado 😁.Vai ter da implementação utilizando o particionamento de Hoare também ?

[@pgdinamica]

Não pretendo fazer vídeo, mas quem sabe um artigo? 🤔

[@matheussousa2548]

Top

[@pgdinamica]

Valeu!

[@williamsilva8779]

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

[@pgdinamica]

Não…o Cormen tem muito conteúdo. Neste outro vídeo, eu conto os tópicos que acho mais importantes: kzbin.info/www/bejne/iaKlmKGDnKuEirc Além destes, eu estudei vários outros algoritmos específicos de computação gráfica, geometria computacional etc (alguns estão no Cormen).

[@thiagoaxel9368]

tem o comb sort que é um bom e rápido algoritmo de ordenação que é uma melhora do buble sort

[@pgdinamica]

Anotado! ✍🏾

[@viniciusmolinagarcia6603]

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]

Não entendi como você quer usar essa ideia no Quicksort, pode explicar um pouco mais?

[@viniciusmolinagarcia6603]

@@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.

[@jonastibulo9647]

Você tem algum vídeo sobre 3-Way Quick Sort?

[@pgdinamica]

Não... 😕

[@naoExiste00]

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?

[@pgdinamica]

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.

[@naoExiste00]

@@pgdinamica Entendi!! Ótima resposta, muito obrigado 🙏🏻

[@danielcolobo]

Mio que tem no YT

[@pgdinamica]

Haha, valeu!

[@barbosa1543]

Eu estou estudando sobre esse algoritmo e achei essa implementação: kzbin.info/www/bejne/oXfIiaqhnNOEb7c 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?

[@lorran5675]

Radix Sort?

[@pgdinamica]

🤔 é uma possibilidade. Obrigado pela sugestão!

[@zazaburotomioka6395]

tendi foi nada :/

[@jqueiroz]

O inventor desse alg. deveria estar preso, mas os gringos se acham tanto, que divulgam seus próprios nomes associados a porcarias como esta.

[@pgdinamica]

? 🫤

[@jairoprates4300]

Você complicou mais do que explicou... a escolha do pivô foi a pior pra explicar esse algoritmo...

[@pgdinamica]

Não concordamos, mas valeu pelo feedback 😉