Pesquisa e Ordenação - Aula 08 - Métodos de Ordenação (Shell sort)

# Pesquisa e Ordenação #Aula 08 – Métodos de Ordenação

(ShellSort)

Prof. Leinylson Fontinele Pereira

Na aula anterior...

Métodos de Ordenação# BucketSort

09:21 Pesquisa e Ordenação: Aula 08 – Métodos de Ordenação (ShellSort)

O que vamos aprender?

Métodos de Ordenação# ShellSort


Vamos começar?

09:21 4Pesquisa e Ordenação: Aula 08 – Métodos de Ordenação (ShellSort)

09:21 5

Ordenação comShellSort

Pesquisa e Ordenação: Aula 08 – Métodos de Ordenação (ShellSort)

Ordenação com ShellSort

09:21

Problema com o algoritmo de ordenação por inserção:

Troca itens adjacentes para determinar o ponto de inserção.

São efetuadas 𝑛 − 1 comparações e movimentações quandoo menor item está na posição mais à direita no vetor.

Permitindo trocas de registros distantes um do outro.



09:21

Os itens separados de ℎ posições são rearranjados

Todo h-ésimo item leva a uma sequência ordenada

Tal sequência é dita estar h-ordenada

Quando ℎ = 1 shellsort corresponde ao algoritmo deinserção



09:34

Como escolher o valor de ℎ:

Sequência para ℎ:ℎ = 3ℎ + 1

Knuth (1973, p. 95) mostrou experimentalmente que esta sequência édifícil de ser batida por mais de 20% em eficiência

A sequência para ℎ corresponde a:

1, 4, 13, 40, 121, 364, 1.093, 3.280, . . .



09:34

Tem como objetivo aumentar o passo de movimento doselementos ao invés das posições adjacentes (passo = 1). Consiste em classificar sub-arquivos do original; Esses sub-arquivos contêm todo k-ésimo elemento do arquivo original; O valor de 𝑘 é chamado de incremento; Ex.: se 𝑘 = 5 , o sub-arquivo consistindo dos elementos𝑥[0], 𝑥[5], 𝑥[10], ... é classificado primeiro.

Cinco sub-arquivos, cada um contendo um quinto dos elementos doarquivo original, são classificados dessa maneira.



09:34

Define-se um novo incremento menor que o anterior;

Gera-se novos sub-arquivos;

Aplica-se novamente o método da inserção nesses novos sub-arquivos.

E assim sucessivamente para novos valores de 𝑘, até 𝑘 = 1.

Sequência de incrementos (definida previamente):ℎ1, ℎ2, … , ℎ𝑡

Com: ℎ𝑡 = 1 𝑒 ℎ𝑖 + 1 < ℎ𝑖 .



09:34Pesquisa e Ordenação: Aula 08 – Métodos de Ordenação (ShellSort)











Criando o histograma


Criando o histograma






Basicamente o algoritmo passa várias vezes pelalista dividindo o grupo maior em menores

Esta divisão é determinada pelo valor calculado dosalto:𝐾 = 𝑘/2

Nos grupos menores é aplicado o método daordenação por inserção


09:34

A razão da eficiência do algoritmo ainda não é conhecida

Ninguém ainda foi capaz de analisar o algoritmo.

A análise contém problemas matemáticos muito difíceis.

A começar pela própria sequência de incrementos

O que se sabe é que cada incremento não deve ser múltiplodo anterior



09:34

Vantagens: Ótima opção para arquivos de tamanho moderado

Sua implementação é simples e requer umaquantidade de código pequena

Complexidade𝑂(𝑛 log 𝑛)



09:34

Desvantagens: O tempo de execução do algoritmo é

sensível à ordem inicial do arquivo

O método não é estável


Concluindo...

09:34 24Pesquisa e Ordenação: Aula 08 – Métodos de Ordenação (ShellSort)

Nesta aula aprendemos...


Métodos de Ordenação# ShellSort

Na próxima aula veremos...


Métodos de Ordenação# RadixSort

Material: https://sites.google.com/site/leinylsonnassau

09:34

Material baseado nas aulas de:

Linguagem C Descomplicada , Dr. André R. Backes

Projeto de Algoritmos, Capítulo 4 – Nívio Ziviani

Métodos de Ordenação, João Luís Garcia Rosa


Alguma Dúvida?

09:34

Até a próxima aula...

[email protected]

Education

Pesquisa e Ordenação - Aula 08 - Métodos de Ordenação (Shell sort)