Estrutura de dados - Ordenação

Estrutura de dados - Ordenação

(Parte 1 de 6)

UFMG/ICEx/DCC AEDS2/1◦ Semestre de 2002

Algoritmos de Ordenação na Memória Principal

Antonio Alfredo Ferreira Loureiro loureiro@dcc.ufmg.br http://www.dcc.ufmg.br/~loureiro

UFMG/ICEx/DCC AEDS2/1◦ Semestre de 2002

Considerações iniciais

• Objetivos:

– Apresentar os métodos de ordenação mais importantes sob o ponto de vista prático

– Mostrar um conjunto amplo de algoritmos para realizar uma mesma tarefa, cada um deles com uma vantagem particular sobre os outros, dependendo da aplicação

• Cada método: – ilustra o uso de estruturas de dados

– mostra como a escolha da estrutura influi nos algoritmos

UFMG/ICEx/DCC AEDS2/1◦ Semestre de 2002

Definição e objetivos da ordenação

• Ordenar corresponde ao processo de rearranjar um conjunto de objetos em uma ordem específica.

• Objetivo da ordenação: – facilitar a recuperação posterior de elementos do conjunto ordenado.

• Exemplos: – Listas telefônicas

– Dicionários

– Índices de livros

– Tabelas e arquivos

UFMG/ICEx/DCC AEDS2/1◦ Semestre de 2002

Observações • Os algoritmos trabalham sobre os registros de um arquivo.

• Apenas uma parte do registro, chamada chave, é utilizada para controlar a ordenação.

• Além da chave podem existir outros componentes em um registro, que não têm influência no processo de ordenar, a não ser pelo fato de que permanecem com a mesma chave.

• O tamanho dos outros componentes pode influenciar na escolha do método ou na forma de implementação de um dado método.

• A estrutura de dados registro é a indicada para representar os elementos a serem ordenados.

UFMG/ICEx/DCC AEDS2/1◦ Semestre de 2002

• Sejam os os itens a1,a2,,an.

Notação

• Ordenar consiste em permutar estes itens em uma ordem

,, akn

tal que, dada uma função de ordenação f, tem-se a seguinte relação:

) ≤≤ f(akn)

• Função de ordenação é definida sobre o campo chave.

UFMG/ICEx/DCC AEDS2/1◦ Semestre de 2002

Notação

• Qualquer tipo de campo chave, sobre o qual exista uma relação de ordem total <, para uma dada função de ordenação, pode ser utilizado.

• A relação < deve satisfazer as condições: – Apenas um de a < b, a = b, a > b é verdade

• A estrutura registro é indicada para representar os itens ai. type ChaveTipo = integer; type Item = record

Chave : ChaveTipo; {outros componentes} end;

UFMG/ICEx/DCC AEDS2/1◦ Semestre de 2002

Observações

• A escolha do tipo da chave como inteiro é arbitrária.

• Qualquer tipo sobre o qual exista uma regra de ordenação bem definida pode ser utilizado. – Tipos usuais são o inteiro e seqüência de caracteres.

• Outros componentes representam dados relevantes sobre o item.

• Um método de ordenação é dito estável, se a ordem relativa dos itens com chaves iguais mantém-se inalterada pelo processo de ordenação.

• Exemplo:

– Se uma lista alfabética de nomes de funcionários de uma empresa é ordenada pelo campo salário, então um método estável produz uma lista em que os funcionários com mesmo salário aparecem em ordem alfabética.

UFMG/ICEx/DCC AEDS2/1◦ Semestre de 2002

Classificação dos métodos de ordenação: Ordenação interna

• Número de registros a serem ordenados é pequeno o bastante para que todo o processo se desenvolva na memória interna (principal) – Qualquer registro pode ser acessado em tempo O(1)

• Organiza os dados na forma de vetores, onde cada dado é “visível”

UFMG/ICEx/DCC AEDS2/1◦ Semestre de 2002

Ordenação interna

• Requisito predominante:

(Parte 1 de 6)

Comentários