Aula16_Metodos_Ordenacao_novo

Prévia do material em texto

Me´todos de Ordenac¸a˜o: Ordenac¸a˜o por Bolha,
Selec¸a˜o Direta e Inserc¸a˜o
Professor:
Silvio Luiz Bragatto Boss
e-mail:
silvioboss@utfpr.edu.br
Universidade Tecnolo´gica Federal do Parana´ - UTFPR
Coordenac¸a˜o de Informa´tica - COINF
Curso de Engenharia de Computac¸a˜o
Disciplina de Estrutura de Dados I
Me´todos de Ordenac¸a˜o
Suma´rio
1 Me´todos de Ordenac¸a˜o
Ordenac¸a˜o por Bolhas
Ordenac¸a˜o por Selec¸a˜o Direta
Ordenac¸a˜o por Inserc¸a˜o
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
BubbleSort - Ordenac¸a˜o por Bolhas
Me´todo de ordenac¸a˜o simples e de entendimento e
implementac¸a˜o fa´ceis;
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
BubbleSort - Ordenac¸a˜o por Bolhas
Me´todo de ordenac¸a˜o simples e de entendimento e
implementac¸a˜o fa´ceis;
Bubblesort esta´ entre os mais conhecidos e difundidos
me´todos de ordenac¸a˜o de arranjos;
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
BubbleSort - Ordenac¸a˜o por Bolhas
Me´todo de ordenac¸a˜o simples e de entendimento e
implementac¸a˜o fa´ceis;
Bubblesort esta´ entre os mais conhecidos e difundidos
me´todos de ordenac¸a˜o de arranjos;
Pore´m na˜o e´ um algoritmo eficiente, e´ estudado para fins de
desenvolvimento de racioc´ınio.
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
BubbleSort - Ordenac¸a˜o por Bolhas
O Princ´ıpio do Bubblesort e´ a troca entre posic¸o˜es
consecutivas, fazendo com que os valores mais altos (ou mais
baixos) “borbulhem” para o final do arranjo (da´ı o nome
Bubblesort);
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
BubbleSort - Ordenac¸a˜o por Bolhas
O Princ´ıpio do Bubblesort e´ a troca entre posic¸o˜es
consecutivas, fazendo com que os valores mais altos (ou mais
baixos) “borbulhem” para o final do arranjo (da´ı o nome
Bubblesort);
Neste exemplo, vamos ordenar o arranjo em ordem crescente
de valores, consideremos inicialmente um arranjo qualquer
desordenado
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
BubbleSort - Ordenac¸a˜o por Bolhas
O primeiro passo e´ se fazer a comparac¸a˜o entre os dois
elementos das primeiras posic¸o˜es :
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
BubbleSort - Ordenac¸a˜o por Bolhas
O primeiro passo e´ se fazer a comparac¸a˜o entre os dois
elementos das primeiras posic¸o˜es :
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
BubbleSort - Ordenac¸a˜o por Bolhas
O primeiro passo e´ se fazer a comparac¸a˜o entre os dois
elementos das primeiras posic¸o˜es :
Assim verificamos que neste caso os dois primeiros elementos
esta˜o desordenados entre si, logo devemos troca´-los de
posic¸a˜o. E assim continuamos com as comparac¸o˜es dos
elementos subsequentes:
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
BubbleSort - Ordenac¸a˜o por Bolhas
O primeiro passo e´ se fazer a comparac¸a˜o entre os dois
elementos das primeiras posic¸o˜es :
Assim verificamos que neste caso os dois primeiros elementos
esta˜o desordenados entre si, logo devemos troca´-los de
posic¸a˜o. E assim continuamos com as comparac¸o˜es dos
elementos subsequentes:
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
BubbleSort - Ordenac¸a˜o por Bolhas
Aqui, mais uma vez, verificamos que os elementos esta˜o
desordenados entre si. Devemos fazer a troca e continuar
nossas comparac¸o˜es ate´ o final do arranjo:
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
BubbleSort - Ordenac¸a˜o por Bolhas
Aqui, mais uma vez, verificamos que os elementos esta˜o
desordenados entre si. Devemos fazer a troca e continuar
nossas comparac¸o˜es ate´ o final do arranjo:
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
BubbleSort - Ordenac¸a˜o por Bolhas
Apo´s este primeiro passo, que compreende a primeira
passagem pelo arranjo fazendo as comparac¸o˜es e as trocas
necessa´rias, verificamos que o maior elemento, o nu´mero 5, foi
parar na u´ltima posic¸a˜o, seu lugar correto no arranjo
ordenado. Pode-se dizer que o nu´mero 5 ”borbulhou”3 para a
sua posic¸a˜o correta, la´ no final do arranjo.
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
BubbleSort - Ordenac¸a˜o por Bolhas
O pro´ximo passo agora sera´ repetir nosso processo de
comparac¸o˜es e trocas desde o in´ıcio do arranjo. So´ que dessa
vez o processo na˜o precisara´ comparar o penu´ltimo com o
u´ltimo elemento, pois o u´ltimo nu´mero, o nu´mero 5, esta´ em
sua posic¸a˜o correta no arranjo. Vamos ao processo :
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
BubbleSort - Ordenac¸a˜o por Bolhas
Novamente se compara os dois primeiros elementos do
arranjo. Neste caso, verificamos que sera´ necessa´ria a troca
de lugares entre os elementos. Em seguida vamos
continuando as comparac¸o˜es ate´ o final
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
BubbleSort - Ordenac¸a˜o por Bolhas
Agora precisaremos repetir o processo novamente, mas desta
vez, ale´m de na˜o precisarmos levar em considerac¸a˜o o u´ltimo
elemento do arranjo (no caso o nu´mero 5 ) que ja´ esta´
ordenado, tambe´m na˜o precisaremos levar em considerac¸a˜o o
penu´ltimo elemento do arranjo (no caso o nu´mero 4) pois ele
tambe´m esta´ em sua posic¸a˜o correta. Vamos enta˜o continuar
o processo :
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
BubbleSort - Ordenac¸a˜o por Bolhas
Mais uma vez o elemento de maior valor, o nu´mero 3,
”borbulhou”para sua posic¸a˜o correta. Basta agora mais um
processo para que todo o arranjo fique ordenado.
Neste caso o arranjo ja´ esta´ ordenado devido as disposic¸o˜es
iniciais de nosso arranjo, mas na˜o e´ poss´ıvel nosso algoritmo
saber se todo o arranjo esta´ ordenado ou na˜o, e e´ exatamente
por isso que precisaremos realizar mais um processo.
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
BubbleSort - Ordenac¸a˜o por Bolhas
programa ordena;
var
vetor1 : vetor [1..5] de inteiros;
i, j, aux: inteiro;
inı´cio
para i de 1 ate´ 5 passo 1 fac¸a
para j de 1 ate´ 5-i passo 1 fac¸a
se vetor1[j] > vetor1[j+1] ent~ao
aux <-- vetor1[j];
vetor1[j] <-- vetor1[j+1];
vetor1[j+1] <-- aux;
fim_se;
fim_para;
fim_para;
fim.
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Ordenac¸a˜o por Selec¸a˜o Direta
O meto´do de ordenac¸a˜o por Selec¸a˜o Direta e´ levemente mais
eficiente que o me´todo Bubblesort, ainda que se trate de um
algoritmo apenas para estudo e ordenac¸a˜o de pequenos
arranjos;
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Ordenac¸a˜o por Selec¸a˜o Direta
O meto´do de ordenac¸a˜o por Selec¸a˜o Direta e´ levemente mais
eficiente que o me´todo Bubblesort, ainda que se trate de um
algoritmo apenas para estudo e ordenac¸a˜o de pequenos
arranjos;
A lo´gica consiste em se varrer o arranjo comparando todos os
seus elementos com o primeiro;
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Ordenac¸a˜o por Selec¸a˜o Direta
O meto´do de ordenac¸a˜o por Selec¸a˜o Direta e´ levemente mais
eficiente que o me´todo Bubblesort, ainda que se trate de um
algoritmo apenas para estudo e ordenac¸a˜o de pequenos
arranjos;
A lo´gica consiste em se varrer o arranjo comparando todos os
seus elementos com o primeiro;
Caso o primeiro elemento esteja desordenado em relac¸a˜o ao
elemento que esta´ sendo comparado com ele no momento, e´
feita a troca;
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos deOrdenac¸a˜o
Ordenac¸a˜o por Selec¸a˜o Direta
O meto´do de ordenac¸a˜o por Selec¸a˜o Direta e´ levemente mais
eficiente que o me´todo Bubblesort, ainda que se trate de um
algoritmo apenas para estudo e ordenac¸a˜o de pequenos
arranjos;
A lo´gica consiste em se varrer o arranjo comparando todos os
seus elementos com o primeiro;
Caso o primeiro elemento esteja desordenado em relac¸a˜o ao
elemento que esta´ sendo comparado com ele no momento, e´
feita a troca;
Ao se chegar ao final do arranjo, teremos o menor valor ou o
maior, conforme a comparac¸a˜o na primeira posic¸a˜o do arranjo.
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Ordenac¸a˜o por Selec¸a˜o Direta
Embora o nu´mero de comparac¸o˜es para o me´todo da bolha e
para o me´todo de selec¸a˜o direta seja o mesmo, o nu´mero de
trocas, no caso me´dio, e´ menor para a ordenac¸a˜o por selec¸a˜o.
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Ordenac¸a˜o por Selec¸a˜o Direta
Neste exemplo vamos ordenar o arranjo em ordem crescente
de valores. Consideremos inicialmente um arranjo qualquer
desordenado:
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Ordenac¸a˜o por Selec¸a˜o Direta
O passo inicial a se dar e´ comparar o primeiro elemento com
todos os outros elementos do arranjo. Comec¸amos
comparando os dois primeiros elementos :
Verifica-se que os dois primeiros elementos esta˜o
desordenados entre si;
Logo devemos troca´-los de posic¸a˜o;
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Ordenac¸a˜o por Selec¸a˜o Direta
Em seguida continuamos a comparar os outros elementos com
o elemento da primeira posic¸a˜o.
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Ordenac¸a˜o por Selec¸a˜o Direta
Aqui, mais uma vez, verificamos que os elementos esta˜o
desordenados entre si;
A troca e´ feita e as comparac¸o˜es continuam.
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Ordenac¸a˜o por Selec¸a˜o Direta
Neste caso percebemos que os elementos ja´ esta˜o ordenados
entre si;
Na˜o e´ feita a troca e se continua as comparac¸o˜es.
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Ordenac¸a˜o por Selec¸a˜o Direta
Apo´s essa primeira etapa, fizemos com que o menor elemento
do arranjo fosse deslocado para primeira posic¸a˜o;
O pro´ximo passo sera´ repetir este mesmo procedimento, so´
que desta vez comparando os elementos do arranjo com o
elemento que esta´ na segunda posic¸a˜o, ja´ que a primeira
posic¸a˜o ja´ foi ordenada.
Neste caso e´ feita a troca pois os elementos esta˜o
desordenados entre si;
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Ordenac¸a˜o por Selec¸a˜o Direta
O procedimento segue.
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Ordenac¸a˜o por Selec¸a˜o Direta
Perceba que desta vez o segundo menor elemento do arranjo
foi deslocado para a segunda posic¸a˜o;
O processo continua com a mesma lo´gica, sem comparar
agora o primeiro e o segundo elementos do arranjo, pois eles
ja´ esta˜o em suas posic¸o˜es corretas;
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Ordenac¸a˜o por Selec¸a˜o Direta
Nestes passos o elemento de menor valor, o nu´mero 3, foi
deslocado para sua posic¸a˜o correta. Mais um processo agora e
todo o arranjo ficara´ ordenado:
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Ordenac¸a˜o por Selec¸a˜o Direta
programa ordena;
var
vetA : vetor [1..5] de inteiros;
i, j, aux: inteiro;
inı´cio
para i de 1 ate´ 4 passo 1 fac¸a
para j de i + 1 ate´ 5 passo 1 fac¸a
se vetA[j] < vetA[i] ent~ao
aux <-- vetA[j];
vetA[j]; <-- vetA[i];
vetA[i]; <-- aux;
fim_se;
fim_para;
fim_para;
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Ordenac¸a˜o por Inserc¸a˜o
para j de 2 ate´ n fac¸a
elemento <-- vetor[j];
i<-- j-1;
enquanto i>0 AND vetor[i]>elemento, fac¸a
vetor[i+1] <-- vetor[i];
i<-- i-1;
fim_enquanto
vetor[i+1] <- elemento;
fim_para
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX