Ordenação - ?· –Heapsort –Ordenação Parcial ∗Seleção Parcial ∗Inserção Parcial ∗Heapsort…

  • Published on
    26-Jan-2019

  • View
    213

  • Download
    0

Embed Size (px)

Transcript

Ordenao

Prof. Jonas Potros

Conceitos Bsicos

Ordenar: processo de rearranjar um conjunto de objetos em uma ordem ascendente ou descendente.

A ordenao visa facilitar a recuperao posterior de itens do conjunto ordenado.

Conceitos Bsicos

A maioria dos mtodos de ordenao baseada em comparaes das chaves.

Existem mtodos de ordenao que utilizam o princpio da distribuio.

Por Distribuio

Exemplo:

Por Distribuio - Algoritmo

1. Distribuir as cartas abertas em treze montes: ases, dois, trs, . . ., reis.

2. Colete os montes na ordem especificada.

3. Distribua novamente as cartas abertas em quatro montes: paus, ouros, copas e espadas.

4. Colete os montes na ordem especificada.

Conceitos Bsicos

Mtodos como o ilustrado so tambm conhecidos como ordenao digital, radixsort ou bucketsort.

Uma das dificuldades de implementar este mtodo est relacionada com o problema de lidar com cada monte.

Se para cada monte ns reservarmos uma rea, ento a demanda por memria extra pode tornar-se proibitiva.

Conceitos Bsicos

O custo para ordenar um arquivo com n elementos da ordem de O(n), dependendo do caso:

3 2 4 6 7 8 9 10

10 9 8 7 6 5 4 2

1 2 3 4 5 6 7 8

Conceitos Bsicos

Notao utilizada nos algoritmos:

Os algoritmos trabalham sobre os registros de um arquivo.

Cada registro possui uma chave utilizada para controlar a ordenao.

Ordenao Interna

Algoritmos

Ordenao por Seleo

Ordenao por Insero

Shellsort

Quicksort

Heapsort

Ordenao Parcial Seleo Parcial Insero Parcial Heapsort Parcial Quicksort Parcial

Introduo

Na escolha de um algoritmo de ordenao internadeve ser considerado o tempo gasto pela ordenao.

3 2 4 6 7 8 9 10

10 9 8 7 6 5 4 2

Introduo

Sendo n o nmero registros no arquivo, as medidas de complexidade relevantes so:

Nmero de comparaes C (n) entre chaves.

Nmero de movimentaes M (n) de item do arquivo.

3 2 4 6 7 8 9 10

10 9 8 7 6 5 4 2

1 2 3 4 5 6 7 8

Introduo

O uso econmico da memria disponvel um requisito primordial na ordenao interna.

Mtodos de ordenao in situ so os preferidos, por utilizarem a estrutura de vetores.

Introduo

Mtodos que utilizam listas encadeadas no so muito utilizados.

Mtodos que fazem cpias dos itens a serem ordenados possuem menor importncia.

Classificao dos mtodos

Simples:

Adequados para pequenos arquivos.

Requerem O(n) comparaes.

Produzem programas pequenos.

Algoritmos: Insertion sort, Selection sort, Bubble sort, Comb sort.

10 9 8 7

1 2 3 4 5 6 8 7

Classificao dos mtodos

Eficientes: Adequados para arquivos maiores.

Requerem O(n log n) comparaes.

Usam menos comparaes.

As comparaes so mais complexas nos detalhes.

Mtodos simples so mais eficientes para pequenos arquivos.

Algoritmos: Merge sort, Heapsort, Shell sort, Radix sort, Gnome sort, Count sort, Bucket sort, Cocktail sort, Timsort e Quick sort

Exemplo: Seleo (Simples)

n=6

Algoritmo:

Selecione o menor item do vetor.

Troque-o com o item da primeira posio do vetor.

Repita essas duas operaes com os n 1 itens restantes, depois com os n 2 itens, at que reste apenas um elemento.

1 2 4 3 7 6

Exemplo: Seleo (Simples)

Anlise

Comparaes entre chaves e movimentaes de registros:

A atribuio min = j executada em mdia n log nvezes, Knuth (1973).

Exemplo: Seleo (Simples)

Vantagens:

Custo linear no tamanho da entrada para o nmero de movimentos de registros.

muito interessante para arquivos pequenos.

Desvantagens:

O fato de o arquivo j estar ordenado no ajuda em nada, pois o custo continua quadrtico.

O algoritmo no estvel.

Exemplo: Insero (Simples)

n=6

Algoritmo:

Em cada passo a partir de i=2 faa:

Selecione o i-simo item da sequncia fonte.

Coloque-o no lugar apropriado na sequncia destino de acordo com o critrio de ordenao.

1 2 4 3 7 6

Exemplo: Insero (Simples)

Anlise

Seja C (n) a funo que conta o nmero de comparaes.

No lao mais interno, na i-sima iterao, o valor de :

Atividade

Implementar o algoritmo de ordenao por Seleo(Select sort) e o por Insero (Insert sort);

Entregar dia 05/03.

Recommended

View more >