Olá, vamos aprender agora uma coisa muito importante ciência da computação, que são os algoritmos de ordenação. Na vida real há inúmeras situações que a gente quer colocar coisas ordem, por exemplo, se eu tenho uma lista de livros, muito provável, uma biblioteca, é muito provável que eu vou querer colocar esses livros ordem, por exemplo, ordem alfabética do sobrenome do autor. Ou se eu tenho uma lista de músicas mp3 eu vou querer colocar elas ordem, por exemplo do título das músicas. Ou se eu tenho uma tabela do campeonato brasileiro de futebol, eu vou querer ordenar os times de acordo com o número de pontos ganhos, de forma que quem tem mais pontos ganhos fica lá no topo da lista e quem tem menos, quem está na lanterninha fica lá baixo. Então, todo momento computação a gente vai estar querendo colocar coisas ordem e existem diferentes algoritmos que a gente pode usar para colocar coisas ordem. Alguns algoritmos são mais simples, são mais fáceis de entender, outros são mais complicados, sofisticados ou difíceis de entender. Alguns algoritmos são mais eficientes e outros são menos eficientes. Vamos começar vendo algoritmo bem simples e depois a gente vai ver alguns outros. Então o primeiro que eu gostaria de mostrar é o algoritmo da Seleção Direta porque eu acredito que é dos algoritmos mais fáceis de entender. Como funciona esse algoritmo da Seleção Direta? É o seguinte, vamos supor que você tem uma lista completa, vamos supor que têm números, por exemplo, nessa lista e a gente quer colocar ordem crescente, então o que é que a gente faz? A cada passo desse algoritmo a gente busca pelo menor elemento do pedaço ainda não ordenado dessa lista e coloca esse menor elemento lá no comecinho desse pedaço. Então, particular, no primeiro passo do algoritmo a gente percorre a lista inteira procurando quem é o menor elemento de todos e daí, coloca esse menor elemento na posição inicial da lista, na primeira posição da lista. E quem estava na posição inicial a gente troca e coloca lá no lugar onde estava aquele outro. Ao terminar de fazer isso a lista já está até a primeira posição ordenada, porque o menor elemento de todos está la na primeira posição é onde ele tem que estar, se a gente vai ordenar ordem crescente. E daí só faltam ordenar N menos elementos, supondo que a lista tem N elementos. E daí, a gente vai para o segundo passo, no segundo passo, a gente olha só para esses N menos buscando qual é o menor elemento desses. O menor desses vai ser o segundo menor elemento da lista, então, a gente coloca ele na segunda posição da lista, trocando de lugar com quem estava lá segundo. Daí, a partir daí, já têm dois elementos ordenados e N menos dois desordenados, e daí a gente repete isso, no terceiro passo a gente vai buscar então nesses N menos menos dois, quem é esse terceiro elemento da lista e coloca ele na terceira posição da lista. Daí, já temos três ordenados e N menos três fora de ordem e a gente vai repetindo isso até terminar a lista, quando a gente chegar lá na última posição, pronto, todos os elementos já vão estar ordem crescente. Para ilustrar isso de uma forma engraçada eu achei na internet vídeo bem engraçado aqui feito pela Universidade de Sapientia, na Romênia, junto com Tirgu Mures Kátai Zoltán e Tóth Lászió. Como que é esse vídeo aqui que eles fizeram, eles pegaram grupo de dança e colocaram para dançar música cigana, que é típica lá da Romênia, e eles têm aqui dez dançarinos numerados de zero a nove e a gente quer ordenar esse vetor, essa lista chamada a, que têm as posições desde a posição zero até a posição nove. E daí ele está rodando aqui o Selection-sort, o algoritmo da Seleção Direta. Então o que é que está acontecendo? Ele está fazendo esse primeiro passo buscando qual é o menor elemento de todos e ele vai comparando a então agora está comparando o zero com o. Agora está comparando o zero com o oito, que está aqui na posição a três. Agora, vai comparar o zero com o sete, então ele vai percorrendo isso até o final, quando ele chegar no final dessa primeira passada, ele vai perceber que o zero é o menor elemento de todos e portanto ele vai colocar o zero nessa posição a de zero. Eu vou adiantar porque ninguém aguenta, tem paciência para ouvir isso, aliás imagina a paciência dos dançarinos para produzir esse vídeo. Aqui está comparando o zero com o nove e agora comparando ali o zero com seis, ele vai descobrir então que o zero é o menor de todos e daí o zero vai lá para a posição a de zero. Vai lá zero! Ele tem que fazer uma festinha, uma dancinha antes, mas daí ele vai para a posição a de zero. Então agora só falta ordenar da posição a de até a de nove. Então a mocinha do três agora vai percorrer todos os outros e vai descobrir quem é o menor. Ela comparou três com o é menor, então agora é o que está sendo comprado com os demais, e o vai até o final agora. Eu não vou ter paciência de assistir tudo isso, então vamos pular aqui bem para frente. Aqui a gente já tem ordenado zero, dois, três, quatro e cinco, todo o comecinho do vetor está ordenado e assim por diante até o final do vídeo, lá no final do vídeo está todo mundo ordenado, eles até fazem uma dancinha para comemorar que está todo mundo ordenado. Haja paciência para fazer vídeo desse. Mas, então vamos agora ver pouco de código Phyton, como que a gente implementaria essa seleção direta código Phyton e eu já implementei aqui antes de gravar esse vídeo, eu fiz uma implementação que eu acho que está funcionando, e a gente vai fazer teste para ver se está funcionando. Então como é que funciona aqui? Eu fiz uma classe chamada Ordenador e dentro dessa classe eu tenho método chamado selecao_direta, e recebe como parâmetro uma lista aqui, esse self aqui você sabe, é o próprio interpretador que vai alimentar o self com com uma referência para o objeto do tipo Ordenador, mas então, a gente só precisa se preocupar com a lista. Então, primeira coisa, eu vou ter essa variável fim onde eu guardo o comprimento da lista e vai ser, eu vou usar ela para saber até onde que eu tenho que ordenar os elementos, que é até o fim da lista. Então, eu começo fazendo for, esse é for que vai fazer os passos principais do algoritmo, aqueles passos que eu mostrei naquele slide. Então, ele vai ter uma variável i que vai indicar qual passo que eu estou, então quando e a gente está vendo, tem o range de fim, vai de zero até fim menos então quando i vale zero ele vai procurar nessa iteração completa, vai percorrer todos os elementos para descobrir o menor de todos e daí, vai guardá-lo na posição zero ali. Depois quando o i vale ele vai procurar pelo segundo menor elemento e vai guardar na segunda posição do vetor, que é a posição lembra que o vetor começa na posição zero. E assim por diante. Então, como é que funciona? Vamos ver dentro aqui do for o que é que está acontecendo dentro do for mais interno. Então, inicialmente a gente supõe que o menor elemento que a gente já viu é o i-ésimo, está na posição i, então a gente guarda ali que a posicao_do_minimo, essa variável vai guardar o índice onde eu encontrei o menor elemento, começa com o i. Daí, eu faço outro for que é pra percorrer desde a posição seguinte ao i, até o final da lista, então por isso eu faço esse for aqui, j vai da posição i mais são os elementos que a gente vai verificar se são menores que aqueles na posição i ou não, até o fim da lista. E a gente faz o seguinte: se o elemento que está na posição j aqui é menor do que o elemento que está na posicao_do_minimo, daí quer dizer que esse elemento que está na posicao_do_minimo não é mais o mínimo o j passa a ser o mínimo, então eu faço posicao_do_minimo = j. Então ao fazer esse for aqui completo até o final do vetor, eu achei agora quem deve entrar lá na posição i da minha lista, que é o i-ésimo, menor elemento do meu vetor. Daí o que é que eu faço? Eu simplesmente coloco esse menor elemento encontrado no início da sublista, e para isso, o que é que eu faço? Eu troco de lugar os elementos nas posições i e posicao_do_minimo. Se fosse outras linguagens de programação, para trocar dois elementos de lugar, trocar o valor de duas variáveis, eu precisaria fazer, guardar numa variável temporária e fazer três operações de atribuição. Phyton é mais simples, numa única linha eu consigo fazer isso. Lembra que Phyton que se eu fizer "a vírgula b recebe b vírgula a", se eu fizer algo desse tipo. Daí o que ele vai fazer é trocar o valor, o valor que estava no a vai para o b e o valor que estava no b vai para o a. Então é isso que eu estou fazendo aqui, estou trocando o elemento da posição i e da posição_do_minimo, eu estou trocando eles de lugar, porque, aqui o que está na posicao_do_minimo vai para o i e o que e o que está no lista de i vai para lista de posicao_do_minimo, então eu estou trocando esses de lugar. Então, fazendo isso a gente tem o algoritmo da Seleção Direta. Será que esse algoritmo está funcionando mesmo? Eu vou ver, vou mandar executar aqui. Salvar, apareceu uma pequena notificação e agora a gente vai fazer teste. Para fazer teste, primeiro deixa eu criar uma lista aqui com os elementos quaisquer ali, numa ordem qualquer também. Então, pronto, criei essa lista aqui, totalmente fora de lugar, então a lista está aqui, os elementos dessa lista agora vamos chamar esse método selecao_direta. Então, primeiro eu vou criar uma instância dessa classe Ordenador, vou chamar de o = Ordenador, então aqui ele cria uma nova instância dessa classe e o passa a ser objeto do tipo ordenador, então eu posso chamar o selecao_direta nesse objeto e ele já está dizendo que eu tenho que passar uma lista como parâmetro e eu vou passar aqui a lista que a gente criou ali. Então, pronto, executou, rapidinho, e agora vou pedir para ver qual o conteúdo da lista, o conteúdo da lista, está ordem crescente. Menos dez, três, oito, dez, 17, 32 e 200. Então, pelo menos nesse caso aqui o nosso algoritmo de ordenação funcionou bem. Então, eu deixo de exercício para vocês agora, experimentar executar esse algoritmo com vetores bem grandes, com umas listas bem grandes. Então cria programinha que gera uma lista de 1000, 2000, 3000 elementos, podem ser elementos aleatórios, ou pode ser uma ordem seguindo alguma regra que você define e daí chama o selecao_direta para ver se o selecao_direta está funcionando. Particular, seria interessante ter método também, que dada uma lista, diz se a lista está ordem crescente ou não, para você conseguir automatizar esse teste. Então, por hoje é só. [MÚSICA] [MÚSICA] [MÚSICA]
