Recursos h

Técnicas de Ordenação

Técnicas de Ordenação
• Ordenação corresponde ao método de rearranjar um conjunto de objetos em uma ordem crescente ou decrescente • Tem como objetivo facilitar a recuperação dos itens do conjunto – Recuperação de nomes em um lista telefônica • Atividade relevante e fundamental em processamento de dados • A comparação é feita através de uma determinada chave escolhida

Classificação – Quanto à Estabilidade
• Instáveis: a ordem relativa dos itens com chaves iguais é alterada durante o processo de ordenação • Estáveis: se a ordem relativa dos itens com chaves iguais mantém-se inalterada durante o processo • Alguns dos métodos de ordenação mais eficientes não são estáveis

Principais Técnicas
QUANTO À ESTABILIDADE

Instáveis:
•SELECT SORT •SHELL SORT •HEAP SORT •QUICK SORT

Estáveis:
ATENÇÃO •BUBBLE SORT •INSERT SORT

Classificação: Quanto ao conjunto de registros
• Ordenação Interna: o conjunto de registros cabe todo em na memória principal • Ordenação Externa: o conjunto de registros não cabe completamente em memória principal, e deve ser armazenado em disco ou fita.
– Alguns autores utilizam ordenação de vetores (ordenação interna) e ordenação de registros (ordenação externa)

Ordenação Interna

Ordenação Interna
• Medidas de complexidade levam em conta:
– O número de comparação entre as chaves – O número de trocas entre os itens

• São classificados em dois tipos:
– Métodos Simples: mais recomendados para conjuntos pequenos de dados. Usam mais comparações, mas produzem códigos menores e mais simples; – Métodos Eficientes ou Sofisticados: adequados para conjuntos maiores de dados. Usam menos comparações, porém produzem códigos mais complexos e com muitos detalhes.

Ordenação Interna
Alguns Algoritmos • • • • Ordenação por Seleção (Selection Sort) Ordenação por Inserção (Insertion Sort) Ordenação por Seleção e Troca (Bubble Sort) Ordenação por Inserção através de incrementos decrescentes (ShellSort) •