Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Algoritmo e Estrutura de Dados

Metodo de Ordenacao - SHELL SORT
by

jhonny carvajal

on 24 October 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Algoritmo e Estrutura de Dados

SHELL SORT 1959 – Criacao : Donald Shell
Universidade de Cincinatti HISTORIA Refinamento – Metodo de Insercao Direta Insercao : Array como único segmento
Shell Sort : Array dividido em varios segmentos public static void shellSort(Integer[] nums) {
int n = nums.length;
int h = n / 2;
int c, j;

while (h > 0) {
for (int i = h; i < n; i++) {
c = nums[i];
j = i;
while (j >= h && nums[j - h] > c) {
nums[j] = nums[j - h];
j = j - h;
}
nums[j] = c;
}
h = h / 2;
}
} Troca itens adjacentes

São efetuadas n − 1 comparações quando o menor item está na posição mais à direita no vetor. Metodo Insercao (falha) (Quando h = 1 Shellsort corresponde aoalgoritmo de inserção.) Knuth (1973) Idealizador da sequencia “h” Sequencia para “h” : h(s) = 3h(s − 1) + 1, para s > 1
h(s) = 1, para s = 1 Analise Shell razão da eficiência não é conhecida.
análise contém problemas matemáticos incremento não deve ser múltiplo do anterior. própria seqüência de incrementos. número de comparações para a seqüência de Knuth: C(n) = O(n^1,25)
C(n) = O(n(ln n)^2) Vantagens Desvantagens: Maior eficiência- tamanho moderado. implementação é simples requer uma quantidade de código pequena. método não é estável tempo de execução sensível à ordem inicial do arquivo Fator Diferencial Algoritmo de Classificação Mais eficiente para metodos Complexidade quadratica ... extensão do algoritmo de ordenação por inserção. ORDENAÇÃO SHELL Quebra sucessiva da sequencia (array ou lista)
Implementacao de ordenacao por insercao na sequencia obtida ... Shell permitindo trocas de registros distantes um do outro. ... Algoritmo passa várias vezes pela lista dividindo o grupo maior em grupos menores.... Os itens separados de “h” posições são rearranjados Metodo de complexidade O(n^2) Menor Eficiencia (grandes sequencias) public static void shellsortMod ( Item v [ ] , int n ) {
int h = 1;

do {
h = h*3 + 1 ;
} while (h < n) ;

do {
h / = 3 ;
for (int i = h + 1 ; i <= n ; i ++) {
Item x = v [ i ] ;
int j = i ;
while ( v [ j -h ] .compara ( x) > 0 ) {
v [ j ] = v [ j-h ] ;
j-= h;
if ( j <= h) break;
}
v [ j ] = x ;
}
} while (h ! = 1 ) ;
} ... Obrigado a todos ... Professor : Virgilio de Oliveira Borges Alexandre Xavier
Christopher Laguna
Lucas Tadeu
Pedro Henrique
Jefferson Junio
Jhonny Carvajal FUNCIONAMENTO Grupos menores : aplicação do método de

I N S E R Ç Ã O (...) Modularização - sequencia "h" 1,4,13,40,121,364,1093,3280,... Analise de complexidade : Pior caso : O (n log ^2 n)
Melhor caso : O (n)
Caso Médio : (depende da sequencia do gap)
Full transcript