Baixe o app para aproveitar ainda mais
Leia os materiais offline, sem usar a internet. Além de vários outros recursos!
Shell Sort
Faça como milhares de estudantes: teste grátis o Passei Direto
Esse e outros conteúdos desbloqueados
16 milhões de materiais de várias disciplinas
Impressão de materiais
Agora você pode testar o
Passei Direto grátis
Faça como milhares de estudantes: teste grátis o Passei Direto
Esse e outros conteúdos desbloqueados
16 milhões de materiais de várias disciplinas
Impressão de materiais
Agora você pode testar o
Passei Direto grátis
Faça como milhares de estudantes: teste grátis o Passei Direto
Esse e outros conteúdos desbloqueados
16 milhões de materiais de várias disciplinas
Impressão de materiais
Agora você pode testar o
Passei Direto grátis
Faça como milhares de estudantes: teste grátis o Passei Direto
Esse e outros conteúdos desbloqueados
16 milhões de materiais de várias disciplinas
Impressão de materiais
Agora você pode testar o
Passei Direto grátis
Faça como milhares de estudantes: teste grátis o Passei Direto
Esse e outros conteúdos desbloqueados
16 milhões de materiais de várias disciplinas
Impressão de materiais
Agora você pode testar o
Passei Direto grátis
Faça como milhares de estudantes: teste grátis o Passei Direto
Esse e outros conteúdos desbloqueados
16 milhões de materiais de várias disciplinas
Impressão de materiais
Agora você pode testar o
Passei Direto grátis
Faça como milhares de estudantes: teste grátis o Passei Direto
Esse e outros conteúdos desbloqueados
16 milhões de materiais de várias disciplinas
Impressão de materiais
Agora você pode testar o
Passei Direto grátis
Faça como milhares de estudantes: teste grátis o Passei Direto
Esse e outros conteúdos desbloqueados
16 milhões de materiais de várias disciplinas
Impressão de materiais
Agora você pode testar o
Passei Direto grátis
Faça como milhares de estudantes: teste grátis o Passei Direto
Esse e outros conteúdos desbloqueados
16 milhões de materiais de várias disciplinas
Impressão de materiais
Agora você pode testar o
Passei Direto grátis
Faça como milhares de estudantes: teste grátis o Passei Direto
Esse e outros conteúdos desbloqueados
16 milhões de materiais de várias disciplinas
Impressão de materiais
Agora você pode testar o
Passei Direto grátis
Compartilhar
Prévia do material em texto
Prof. Aleffer Rocha Proposto por Donald Shell em 1959. Trata-se de uma extensão do Insertion Sort. Os itens que estão separados por ℎ posições são rearranjados de tal forma que todo ℎ -ésimo item leva a uma sequência ordenada. Tal sequência é dita estar ℎ-ordenada. Para esta aula, utilizamos ℎ = ⌊𝑛/2⌋, ℎ = ⌊𝑛/2⌋, …, ℎ = 1. Onde 𝑛 é a quantidade de itens no vetor. 1 20 3 4 5v[6] = 34 13 51 0 78 14 1 20 3 4 5v[6] = 34 13 51 0 78 14 h = ⌊𝒏/𝟐⌋ = 𝟐 1 20 3 4 5v[6] = 34 13 51 0 78 14 h = ⌊𝒏/𝟐⌋ = 𝟐 1 20 3 4 5v[6] = 34 13 51 0 78 14 h = 2 1 20 3 4 5v[6] = 34 13 51 0 78 14 h = 2 1 20 3 4 5v[6] = 34 13 51 0 78 14 h = 2 1 20 3 4 5v[6] = 34 13 51 0 78 14 h = 2 1 20 3 4 5v[6] = 34 13 51 0 78 14 h = 2 1 20 3 4 5v[6] = 34 0 51 13 78 14 h = 2 1 20 3 4 5v[6] = 34 0 51 13 78 14 h = 2 1 20 3 4 5v[6] = 34 0 51 13 78 14 h = 2 1 20 3 4 5v[6] = 34 0 51 13 78 14 h = 2 1 20 3 4 5v[6] = 34 0 51 13 78 14 h = 2 h = ⌊𝟐/𝟐⌋ = 𝟏 1 20 3 4 5v[6] = 34 0 51 13 78 14 h = 2 h = 1 1 20 3 4 5v[6] = 34 0 51 13 78 14 h = 2 h = 1 1 20 3 4 5v[6] = 34 0 51 13 78 14 h = 2 h = 1 1 20 3 4 5v[6] = 34 0 51 13 78 14 h = 2 h = 1 1 20 3 4 5v[6] = 34 0 51 13 78 14 h = 2 h = 1 1 20 3 4 5v[6] = 34 0 51 13 78 14 h = 2 h = 1 1 20 3 4 5v[6] = 340 51 13 78 14 h = 2 h = 1 1 20 3 4 5v[6] = 340 51 13 78 14 h = 2 h = 1 1 20 3 4 5v[6] = 340 51 13 78 14 h = 2 h = 1 1 20 3 4 5v[6] = 340 13 51 78 14 h = 2 h = 1 1 20 3 4 5v[6] = 340 13 51 78 14 h = 2 h = 1 1 20 3 4 5v[6] = 340 13 51 78 14 h = 2 h = 1 1 20 3 4 5v[6] = 130 34 51 78 14 h = 2 h = 1 1 20 3 4 5v[6] = 130 34 51 78 14 h = 2 h = 1 1 20 3 4 5v[6] = 130 34 51 78 14 h = 2 h = 1 1 20 3 4 5v[6] = 130 34 51 78 14 h = 2 h = 1 1 20 3 4 5v[6] = 130 34 51 78 14 h = 2 h = 1 1 20 3 4 5v[6] = 130 34 51 78 14 h = 2 h = 1 1 20 3 4 5v[6] = 130 34 51 14 78 h = 2 h = 1 1 20 3 4 5v[6] = 130 34 51 14 78 h = 2 h = 1 1 20 3 4 5v[6] = 130 34 51 14 78 h = 2 h = 1 1 20 3 4 5v[6] = 130 34 51 14 78 h = 2 h = 1 1 20 3 4 5v[6] = 130 34 14 51 78 h = 2 h = 1 1 20 3 4 5v[6] = 130 34 14 51 78 h = 2 h = 1 1 20 3 4 5v[6] = 130 34 14 51 78 h = 2 h = 1 1 20 3 4 5v[6] = 130 34 14 51 78 h = 2 h = 1 1 20 3 4 5v[6] = 130 14 34 51 78 h = 2 h = 1 1 20 3 4 5v[6] = 130 14 34 51 78 h = 2 h = 1 1 20 3 4 5v[6] = 130 14 34 51 78 h = 2 h = 1 1 20 3 4 5v[6] = 130 14 34 51 78 h = 2 h = 1 1 20 3 4 5v[6] = 130 14 34 51 78 1 20 3 4 5v[6] = 34 13 51 0 78 14 1 20 3 4 5v[6] = 1 20 3 4 5v[6] = 7851340 13 14 130 1434 7851h = 2 inicial h = 1 Início ShellSort(v[], ini, fim) h = (fim-ini+2)/2; Enquanto h > 0 faça i = h; Enquanto i <= (fim-ini+1) faça aux = v[i]; j = i; Enquanto j >=h e aux < v[j-h] faça v[j] = v[j-h]; j = j – h; Fim Enquanto v[j] = aux; i = i + 1; Fim Enquanto h = h / 2; Fim Enquanto Fim ShellSort Qual a ordem de grandeza no pior caso do algoritmo Shell Sort? 𝑂(𝑛2) onde 𝑛 é a quantidade de elementos no vetor. • ZIVIANI, Nivio et al. Projeto de algoritmos: com implementações em Pascal e C. Thomson, 2004. ESTRUTURA DE DADOS 1 SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT SHELL SORT MATERIAL UTILIZADO
Continue navegando
Materiais relacionados
36 pág.
171 pág.
Perguntas relacionadas
Compartilhar