Bem vindo ao curso de Introdução à Ciência da Computação destinado aos alunos regulares da Universidade de São Paulo! Esta é a segunda parte do Curso, onde você vai continuar a aprender os principais conceitos introdutórios de Ciência da Computação e também aprenderá a desenvolver pequenos programas na linguagem Python. Esta disciplina não possui pré-requisitos; não é esperado que você tenha qualquer experiência prévia em programação; ela exige apenas o conhecimento dos conceitos básicos de matemática do ensino fundamental. No entanto, você deve fazer a primeira parte do Curso (também disponível aqui no Coursera). O objetivo principal é desenvolver o raciocínio aplicado na formulação e resolução de problemas computacionais, ensinar como abordar e resolver problemas computacionais. O ato de programar é uma ferramenta útil para trabalhar o raciocínio mencionado acima, bem como tornar mais concretos outros conceitos comuns em ciência da computação. Ao término do curso, o aluno estará capacitado para escrever pequenos programas em Python e a continuar com estudos mais avançados sobre Python por conta própria usando material disponível na Web. Bom curso!
Algoritmo de Ordenação Seleção Direta
Loading...
Do curso por Universidade de São Paulo
Introdução à Ciência da Computação com Python Parte 2
274 classificações
Na lição
Algoritmos de Busca e Ordenação. Complexidade Computacional
Olá! Vimos até agora como armazenar e manipular os dados na memória, usando estruturas como listas e matrizes, na primeira parte do curso. Tão importante quanto saber armazenar os dados é conseguir organizá-los e recuperá-los quando necessário. Nessa semana iremos estudar alguns algoritmos de busca e ordenação. Mãos à obra ;-)
Conheça os instrutores
Fabio KonProfessor Titular
Departamento de Ciência da Computação - IME
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]
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
