Aula18_Ordenacao_ShellSort_QuickSort

Prévia do material em texto

Me´todos de Ordenac¸a˜o: ShellSort e QuickSort
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
Shell Sort
Quick Sort
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Shell Sort
Proposto por Shell em 1959;
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Shell Sort
Proposto por Shell em 1959;
E´ uma extensa˜o do algoritmo de 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
Shell Sort
Proposto por Shell em 1959;
E´ uma extensa˜o do algoritmo de ordenac¸a˜o por inserc¸a˜o;
Problema com o algoritmo de 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
Shell Sort
Proposto por Shell em 1959;
E´ uma extensa˜o do algoritmo de ordenac¸a˜o por inserc¸a˜o;
Problema com o algoritmo de ordenac¸a˜o por inserc¸a˜o:
Troca itens adjacentes para determinar o ponto de inserc¸a˜o;
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Shell Sort
Proposto por Shell em 1959;
E´ uma extensa˜o do algoritmo de ordenac¸a˜o por inserc¸a˜o;
Problema com o algoritmo de ordenac¸a˜o por inserc¸a˜o:
Troca itens adjacentes para determinar o ponto de inserc¸a˜o;
Sa˜o efetuadas n-1 comparac¸o˜es e movimentac¸o˜es quando o
menor item esta´ na posic¸a˜o mais a` direita no vetor.
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Shell Sort
Proposto por Shell em 1959;
E´ uma extensa˜o do algoritmo de ordenac¸a˜o por inserc¸a˜o;
Problema com o algoritmo de ordenac¸a˜o por inserc¸a˜o:
Troca itens adjacentes para determinar o ponto de inserc¸a˜o;
Sa˜o efetuadas n-1 comparac¸o˜es e movimentac¸o˜es quando o
menor item esta´ na posic¸a˜o mais a` direita no vetor.
O me´todo de Shell contorna este problema permitindo trocas
de registros distantes um do outro.
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Shell Sort
Ao inve´s de possuir apenas uma lista, no shellsort existem
va´rias listas;
Assumindo que existe uma sequencia de nu´meros 12 43 1 6
56 23 52 9.
Esta sequencia (lista) sera´ quebrada em va´rias listas baseada
num “pulo” de um nu´mero para outro.
Por exemplo: com pulo valendo 4, teremos os nu´meros
selecionados de 4 em quatro posic¸o˜es.
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Shell Sort
Como escolher o pulo ?
O valor escolhido para o “pulo” muda os valores obtidos na
sequencia e tambe´m ira´ impactar na quantidade de testes de o
algoritmo precisa fazer para encontrar a soluc¸a˜o final;
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Shell Sort
Como escolher o pulo ?
O valor escolhido para o “pulo” muda os valores obtidos na
sequencia e tambe´m ira´ impactar na quantidade de testes de o
algoritmo precisa fazer para encontrar a soluc¸a˜o final;
Existem alguns estudos na literatura para obter uma soluc¸a˜o
o´tima do algoritmo em func¸a˜o da escolha do valor de “pulo”;
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Shell Sort
Como escolher o pulo ?
O valor escolhido para o “pulo” muda os valores obtidos na
sequencia e tambe´m ira´ impactar na quantidade de testes de o
algoritmo precisa fazer para encontrar a soluc¸a˜o final;
Existem alguns estudos na literatura para obter uma soluc¸a˜o
o´tima do algoritmo em func¸a˜o da escolha do valor de “pulo”;
No nosso estudo, utilizaremos uma forma fa´cil de escolher o
valor de pulo e que e´ claro, na˜o ser a melhor soluc¸a˜o poss´ıvel;
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Shell Sort
Como escolher o pulo ?
O valor escolhido para o “pulo” muda os valores obtidos na
sequencia e tambe´m ira´ impactar na quantidade de testes de o
algoritmo precisa fazer para encontrar a soluc¸a˜o final;
Existem alguns estudos na literatura para obter uma soluc¸a˜o
o´tima do algoritmo em func¸a˜o da escolha do valor de “pulo”;
No nosso estudo, utilizaremos uma forma fa´cil de escolher o
valor de pulo e que e´ claro, na˜o ser a melhor soluc¸a˜o poss´ıvel;
Em virtude da quantidade de comparac¸o˜es e trocas de
elementos ser uma func¸a˜o da escolha deste nu´mero, a
complexidade deste me´todo e´ dif´ıcil de representar;
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Shell Sort
Como escolher o pulo ?
O valor escolhido para o “pulo” muda os valores obtidos na
sequencia e tambe´m ira´ impactar na quantidade de testes de o
algoritmo precisa fazer para encontrar a soluc¸a˜o final;
Existem alguns estudos na literatura para obter uma soluc¸a˜o
o´tima do algoritmo em func¸a˜o da escolha do valor de “pulo”;
No nosso estudo, utilizaremos uma forma fa´cil de escolher o
valor de pulo e que e´ claro, na˜o ser a melhor soluc¸a˜o poss´ıvel;
Em virtude da quantidade de comparac¸o˜es e trocas de
elementos ser uma func¸a˜o da escolha deste nu´mero, a
complexidade deste me´todo e´ dif´ıcil de representar;
Sabe-se que a complexidade, no pior caso, para a pior escolha
de valor de “pulo” sera´ O(n2).
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Shell Sort
void shellsort (int a[], int n) {
int i, j, k, h, v;
h=1;
do {
h = 3*h+1;
} while(h < n);
do {
h =h / 3;
for (i=h; i<n; i++) {
v=a[i];
j=i;
while (j>=h && a[j-h]>v){
a[j]=a[j-h];
j=j-h; }
a[j]=v; }
}while (h >1);
}
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Quicksort – Ordenac¸a˜o Ra´pida
Me´todo proposto por C. A. Hoare, em 1962, na Universidade
de Moscou;
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Quicksort – Ordenac¸a˜o Ra´pida
Me´todo proposto por C. A. Hoare, em 1962, na Universidade
de Moscou;
E´ considerado o me´todo de ordenac¸a˜o mais eficiente ate´ hoje;
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Quicksort – Ordenac¸a˜o Ra´pida
Me´todo proposto por C. A. Hoare, em 1962, na Universidade
de Moscou;
E´ considerado o me´todo de ordenac¸a˜o mais eficiente ate´ hoje;
Utiliza a estrate´gia “dividir para conquistar”;
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Quicksort – Ordenac¸a˜o Ra´pida
Me´todo proposto por C. A. Hoare, em 1962, na Universidade
de Moscou;
E´ considerado o me´todo de ordenac¸a˜o mais eficiente ate´ hoje;
Utiliza a estrate´gia “dividir para conquistar”;
Dividir um problema em subproblemas menores e combinar as
soluc¸o˜es a fim de se obter a soluc¸a˜o do problema original;
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Quicksort – Ordenac¸a˜o Ra´pida
O me´todo consiste em:
Escolher um pivoˆ inicial x;
Colocar todos itens com chave menor que a de x a` esquerda
de x, formando uma sequeˆncia S1;
Colocar todos itens com chave maior que a de x a` direita de x,
formando uma sequeˆncia S2;
Isto feito, o mesmo processo e´ aplicado a`s sequeˆncias S1 e S2,
que por sua vez produzira˜o novos segmentos;
O processo deve ser aplicado sucessivamente a`s sequeˆncias
enquanto elas tiverem tamanho > 1.
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX
Me´todos de Ordenac¸a˜o
Quicksort – Ordenac¸a˜o Ra´pida
void quickSort(int vet[], int min, int max){
if(min >= max) //array ordenado
return;
int i = min; j = max;
int pivo = vet[(i+j)/2]; // valor do elemento central
do{ //Dividir em duas partes
while(vet[i] < pivo) i++;
while(vet[j] > pivo) j--;
if(i<=j){
if(vet[i] != vet[j])troca(&vet[i],&vet[j]);
i++;
j--
}
}while(i<=j);
quickSort(vet,min,j); //ordenar parte esquerda
quickSort(vet,i,max); //ordenar parte direita
}
Silvio Luiz Bragatto Boss UTFPR
Me´todos de Ordenac¸a˜o LATEX