estudante

868 palavras 4 páginas
Projeto de Algoritmos – Cap.4 Ordenação

Introdução - Conceitos Básicos
• Ordenar: processo de rearranjar um conjunto de objetos em uma ordem ascendente ou descendente.
• A ordenação visa facilitar a recuperação posterior de itens do conjunto ordenado. – Dificuldade de se utilizar um catálogo telefônico se os nomes das pessoas não estivessem listados em ordem alfabética.
• Notação utilizada nos algoritmos:
– Os algoritmos trabalham sobre os registros de um arquivo.
– Cada registro possui uma chave utilizada para controlar a ordenação. – Podem existir outros componentes em um registro.

2

Projeto de Algoritmos – Cap.4 Ordenação

Introdução - Conceitos Básicos
• Estrutura de um registro: typedef long TipoChave; typedef struct TipoItem {
TipoChave Chave;
/∗ outros componentes ∗/
} TipoItem ;

• Qualquer tipo de chave sobre o qual exista uma regra de ordenação bem-definida pode ser utilizado.
• Um método de ordenação é estável se a ordem relativa dos itens com chaves iguais não se altera durante a ordenação.
• Alguns dos métodos de ordenação mais eficientes não são estáveis.
• A estabilidade pode ser forçada quando o método é não-estável.
• Sedgewick (1988) sugere agregar um pequeno índice a cada chave antes de ordenar, ou então aumentar a chave de alguma outra forma.

3

Projeto de Algoritmos – Cap.4 Ordenação

Introdução - Conceitos Básicos
• Classificação dos métodos de ordenação:
– Interna: arquivo a ser ordenado cabe todo na memória principal.
– Externa: arquivo a ser ordenado não cabe na memória principal.
• Diferenças entre os métodos:
– Em um método de ordenação interna, qualquer registro pode ser imediatamente acessado.
– Em um método de ordenação externa, os registros são acessados seqüencialmente ou em grandes blocos.
• A maioria dos métodos de ordenação é baseada em comparações das chaves.
• Existem métodos de ordenação que utilizam o princípio da distribuição. 4

Projeto de Algoritmos – Cap.4

Relacionados

  • Estudante
    4061 palavras | 17 páginas
  • Estudante
    5203 palavras | 21 páginas
  • estudante
    1826 palavras | 8 páginas
  • Estudante
    1976 palavras | 8 páginas
  • estudante
    4108 palavras | 17 páginas
  • Estudante
    4793 palavras | 20 páginas
  • estudantes
    7348 palavras | 30 páginas
  • estudante
    16461 palavras | 66 páginas
  • estudante
    1462 palavras | 6 páginas
  • Estudante
    1075 palavras | 5 páginas