Ordenação de dados

UFSC-CTC-INE
INE5384 - Estruturas de Dados

Ordenação de Dados

Prof. Ronaldo S. Mello
2002/2

Ordenação de Dados
•
•

Processo bastante utilizado na computação de uma estrutura de dados
Dados ordenados garantem uma melhor performance de pesquisa a uma ED
– busca seqüencial
•

evita a varredura completa de uma lista de dados

– busca binária
•
•

só é possível se os dados estão ordenados apresenta baixa complexidade

1

Compromisso
• “A complexidade da ordenação da ED não deve exceder a complexidade da computação a ser feita na ED sem o processo de ordenação”
• Exemplo: deseja-se realizar uma única pesquisa a um vetor
– busca seqüencial ⇒ O(n)
– ordenação ⇒ O(n log n)
– Não vale a pena ordenar!

Considerações
•
•

Dados estão mantidos em um vetor
Elemento do vetor
– objeto que possui um atributo chave que deve ser mantido ordenado

•

•

Um método troca(x,y) realiza a troca dos elementos presentes nas posições x e y do vetor Para fins de exemplo, números inteiros serão utilizados como elementos

2

Implementação

Classe Ordenador início vetor inteiro[ ]; n inteiro; /* tamanho do vetor */

construtor Ordenador (REF v[ ] inteiro); início n ← v.lenght; se n < 1 então Exceção VetorVazio(); vetor ← v; ordena(); v ← vetor; fim; método ordena(); início fim; fim; Implementação
Classe Ordenador início ... método troca(x inteiro, y inteiro); início aux inteiro; aux ← vetor[x]; vetor[x] ← vetor[y]; vetor[y] ← aux; fim; fim;

3

Métodos de Ordenação
• Ordenação por troca
– BubbleSort (método da bolha)
– QuickSort (método da troca e partição)

• Ordenação por inserção
– InsertionSort (método da inserção direta)
– BinaryInsertionSort (método da inserção direta binária)

• Ordenação por seleção
– SelectionSort (método da seleção direta)
– HeapSort (método da seleção em árvore)

• Outros métodos
– MergeSort (método da intercalação)
– BucketSort (método da