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 RU-vid, 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+.
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 😊
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.
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
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 ```
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
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?
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: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-SqBgnMgFQTU.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).
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: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-kFeXwkgnQ9U.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?
