ordenacao shellsort quicksort em C

Metodos de Ordenacao: ShellSort e QuickSort

Professor:

Silvio Luiz Bragatto Boss

e-mail:

silvioboss@utfpr.edu.br

Universidade Tecnologica Federal do Parana - UTFPR

Coordenacao de Informatica - COINF

Curso de Engenharia de Computacao

Disciplina de Estrutura de Dados I

Metodos de Ordenacao

Sumario

1 Metodos de OrdenacaoShell SortQuick Sort

Silvio Luiz Bragatto Boss UTFPR

Metodos de Ordenacao LATEX

Metodos de Ordenacao

Shell Sort

Proposto por Shell em 1959;

Silvio Luiz Bragatto Boss UTFPR

Metodos de Ordenacao LATEX

Metodos de Ordenacao

Shell Sort

Proposto por Shell em 1959;

E uma extensao do algoritmo de ordenacao por insercao;

Silvio Luiz Bragatto Boss UTFPR

Metodos de Ordenacao LATEX

Metodos de Ordenacao

Shell Sort

Proposto por Shell em 1959;

E uma extensao do algoritmo de ordenacao por insercao;

Problema com o algoritmo de ordenacao por insercao:

Silvio Luiz Bragatto Boss UTFPR

Metodos de Ordenacao LATEX

Metodos de Ordenacao

Shell Sort

Proposto por Shell em 1959;

E uma extensao do algoritmo de ordenacao por insercao;

Problema com o algoritmo de ordenacao por insercao:

Troca itens adjacentes para determinar o ponto de insercao;

Silvio Luiz Bragatto Boss UTFPR

Metodos de Ordenacao LATEX

Metodos de Ordenacao

Shell Sort

Proposto por Shell em 1959;

E uma extensao do algoritmo de ordenacao por insercao;

Problema com o algoritmo de ordenacao por insercao:

Troca itens adjacentes para determinar o ponto de insercao;Sao efetuadas n-1 comparacoes e movimentacoes quando omenor item esta na posicao mais a direita no vetor.

Silvio Luiz Bragatto Boss UTFPR

Metodos de Ordenacao LATEX

Metodos de Ordenacao

Shell Sort

Proposto por Shell em 1959;

E uma extensao do algoritmo de ordenacao por insercao;

Problema com o algoritmo de ordenacao por insercao:

Troca itens adjacentes para determinar o ponto de insercao;Sao efetuadas n-1 comparacoes e movimentacoes quando omenor item esta na posicao mais a direita no vetor.

O metodo de Shell contorna este problema permitindo trocasde registros distantes um do outro.

Silvio Luiz Bragatto Boss UTFPR

Metodos de Ordenacao LATEX

Metodos de Ordenacao

Shell Sort

Ao inves de possuir apenas uma lista, no shellsort existemvarias listas;

Assumindo que existe uma sequencia de numeros 12 43 1 6

56 23 52 9.

Esta sequencia (lista) sera quebrada em varias listas baseadanum “pulo” de um numero para outro.

Por exemplo: com pulo valendo 4, teremos os numerosselecionados de 4 em quatro posicoes.

Silvio Luiz Bragatto Boss UTFPR

Metodos de Ordenacao LATEX

Metodos de Ordenacao

Shell Sort

Como escolher o pulo ?

O valor escolhido para o “pulo” muda os valores obtidos nasequencia e tambem ira impactar na quantidade de testes de oalgoritmo precisa fazer para encontrar a solucao final;

Silvio Luiz Bragatto Boss UTFPR

Metodos de Ordenacao LATEX

Metodos de Ordenacao

Shell Sort

Como escolher o pulo ?

O valor escolhido para o “pulo” muda os valores obtidos nasequencia e tambem ira impactar na quantidade de testes de oalgoritmo precisa fazer para encontrar a solucao final;

Existem alguns estudos na literatura para obter uma solucaootima do algoritmo em funcao da escolha do valor de “pulo”;

Silvio Luiz Bragatto Boss UTFPR

Metodos de Ordenacao LATEX

Metodos de Ordenacao

Shell Sort

Como escolher o pulo ?

O valor escolhido para o “pulo” muda os valores obtidos nasequencia e tambem ira impactar na quantidade de testes de oalgoritmo precisa fazer para encontrar a solucao final;

Existem alguns estudos na literatura para obter uma solucaootima do algoritmo em funcao da escolha do valor de “pulo”;

No nosso estudo, utilizaremos uma forma facil de escolher ovalor de pulo e que e claro, nao ser a melhor solucao possıvel;

Silvio Luiz Bragatto Boss UTFPR

Metodos de Ordenacao LATEX

Metodos de Ordenacao

Shell Sort

Como escolher o pulo ?

O valor escolhido para o “pulo” muda os valores obtidos nasequencia e tambem ira impactar na quantidade de testes de oalgoritmo precisa fazer para encontrar a solucao final;

Existem alguns estudos na literatura para obter uma solucaootima do algoritmo em funcao da escolha do valor de “pulo”;

No nosso estudo, utilizaremos uma forma facil de escolher ovalor de pulo e que e claro, nao ser a melhor solucao possıvel;

Em virtude da quantidade de comparacoes e trocas deelementos ser uma funcao da escolha deste numero, acomplexidade deste metodo e difıcil de representar;

Silvio Luiz Bragatto Boss UTFPR

Metodos de Ordenacao LATEX

Metodos de Ordenacao

Shell Sort

Como escolher o pulo ?

O valor escolhido para o “pulo” muda os valores obtidos nasequencia e tambem ira impactar na quantidade de testes de oalgoritmo precisa fazer para encontrar a solucao final;

Existem alguns estudos na literatura para obter uma solucaootima do algoritmo em funcao da escolha do valor de “pulo”;

No nosso estudo, utilizaremos uma forma facil de escolher ovalor de pulo e que e claro, nao ser a melhor solucao possıvel;

Em virtude da quantidade de comparacoes e trocas deelementos ser uma funcao da escolha deste numero, acomplexidade deste metodo e difıcil de representar;

Sabe-se que a complexidade, no pior caso, para a pior escolhade valor de “pulo” sera O(n2).

Silvio Luiz Bragatto Boss UTFPR

Metodos de Ordenacao LATEX

Metodos de Ordenacao

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

Metodos de Ordenacao LATEX

Metodos de Ordenacao

Quicksort – Ordenacao Rapida

Metodo proposto por C. A. Hoare, em 1962, na Universidadede Moscou;

Silvio Luiz Bragatto Boss UTFPR

Metodos de Ordenacao LATEX

Metodos de Ordenacao

Quicksort – Ordenacao Rapida

Metodo proposto por C. A. Hoare, em 1962, na Universidadede Moscou;

E considerado o metodo de ordenacao mais eficiente ate hoje;

Silvio Luiz Bragatto Boss UTFPR

Metodos de Ordenacao LATEX

Metodos de Ordenacao

Quicksort – Ordenacao Rapida

Metodo proposto por C. A. Hoare, em 1962, na Universidadede Moscou;

E considerado o metodo de ordenacao mais eficiente ate hoje;

Utiliza a estrategia “dividir para conquistar”;

Silvio Luiz Bragatto Boss UTFPR

Metodos de Ordenacao LATEX

Metodos de Ordenacao

Quicksort – Ordenacao Rapida

Metodo proposto por C. A. Hoare, em 1962, na Universidadede Moscou;

E considerado o metodo de ordenacao mais eficiente ate hoje;

Utiliza a estrategia “dividir para conquistar”;

Dividir um problema em subproblemas menores e combinar assolucoes a fim de se obter a solucao do problema original;

Silvio Luiz Bragatto Boss UTFPR

Metodos de Ordenacao LATEX

Metodos de Ordenacao

Quicksort – Ordenacao Rapida

O metodo consiste em:

Escolher um pivo inicial x;

Colocar todos itens com chave menor que a de x a esquerdade x, formando uma sequencia S1;

Colocar todos itens com chave maior que a de x a direita de x,formando uma sequencia S2;

Isto feito, o mesmo processo e aplicado as sequencias S1 e S2,que por sua vez produzirao novos segmentos;

O processo deve ser aplicado sucessivamente as sequenciasenquanto elas tiverem tamanho > 1.

Silvio Luiz Bragatto Boss UTFPR

Metodos de Ordenacao LATEX

Metodos de Ordenacao

Quicksort – Ordenacao Rapida

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

Metodos de Ordenacao LATEX