Ordenação

UFMG/ICEx/DCC

AEDS2/1◦ Semestre de 2002

Algoritmos de Ordenação na
Memória Principal
Antonio Alfredo Ferreira Loureiro [e-mail] http://www.dcc.ufmg.br/~loureiro

AEDS2/1◦ Semestre de 2002

UFMG/ICEx/DCC

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

AEDS2/1◦ Semestre de 2002

UFMG/ICEx/DCC

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

AEDS2/1◦ Semestre de 2002

UFMG/ICEx/DCC

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.

AEDS2/1◦ Semestre de 2002

UFMG/ICEx/DCC

Notação
• Sejam os os itens a1, a2, . . . , an.
• Ordenar consiste em permutar estes itens em uma ordem a k1 , a k2 , . . . , a kn tal que, dada uma função de ordenação f , tem-se a seguinte relação: f (ak1 ) ≤ f (ak2 ) ≤ . . . ≤ f (akn )
• Função de ordenação é definida sobre o campo chave.

AEDS2/1◦ Semestre de 2002