Os Métodos de Ordenação

Métodos de Ordenação

Aluno: Douglas Rodrigues Oliveira

Orientador: Prof. Michel Pires Silva

[pic 1]

Resumo

Este artigo tem o objetivo, analisar e descrever sobre os m´métodos de ordenação apresentados em sala de aula, sendo eles: Seleciona Short, Insertion Short, Shell Short, Merge Short, Quick Short, Heap Short e Radix Short, esses m´métodos foram apresentados na linguagem pascal, no qual foram realizados teste de eficiência com arquivos diversos contendo várias palavras (20, 500, 1.000, 10.000, 100.000, 1.000.000, 10.000.000) desordenadas, e ordenadas em ordem lexicográfica. Neste teste foram obtidos os tempos, que foram usados para calcular a média e ver a diferença entre esses métodos.

[pic 2]

1. Introdução

De acordo com Nívio Ziviani: ”Ordenar corresponde ao processo de rearranjar um conjunto de objetos em uma ordem ascendente ou descendente. O objetivo principal da ordenação é facilitar a recuperação posterior de itens do conjunto ordenado... A atividade de colocar as coisas em ordem está presente na maioria das aplicações onde os objetos armazenados têm que ser pesquisados e recuperados, tais como dicionários, índices de livros, tabelas e arquivos. ”

M´métodos de Ordenação são utilizados com o objetivo de organizar de forma crescente ou decrescente uma quantidade especifica de dados, fazendo com que facilite a busca do dado desejado neste grupo de dados. Os métodos de ordenação podem ser classificados como estáveis e não estáveis:

Estáveis: Quando a ordem dos itens com chaves iguais e já ordenados, ou seja, itens que seja igual ao item que esta´ sendo comparado, não são modificados durante o processo de ordenação.

Não estáveis: As ordens dos dados iguais são alteradas durante a execução do método de ordenação. Nesse contexto, se for o caso, ´e preciso forçar sua estabilidade.

[pic 3]

Figura 1: Exemplo de ordenação Estável e Instável

Centro Universitário de Formiga        9 de junho de 2014

Os métodos de ordenação são classificados em dois grandes grupos: ordenação interna e externa.

Ordenação Interna: São os m´métodos que não necessitam de uma memória secundária para o processo, a ordenação é feita na memória principal do computador;

Ordenação Externa: Quando o arquivo a ser ordenado não cabe na memória principal e, por isso, tem de ser armazenado em fita ou disco.

A principal diferença entre os dois grupos, ´e que em ordenação interna, qualquer registro pode ser imediatamente acessado. Já em ordenação externa os registros são acessados sequencialmente ou em grandes blocos.

Esses métodos de ordenação geram também um custo computacional, que será comentado em breve, em análise assintótica. Abaixo, será falado resumidamente sobre cada um dos métodos anteriormente apresentado:

• Seleciona Short: É um dos métodos de ordenação, mas simples encontrado na computação, que se basear em passar sempre o menor valor para a primeira posição, o segundo menor valor para segunda posição, e assim sucessivamente, até que reste apenas um elemento. E um método bastante usado para trabalhar com arquivos pequenos.
• Insertion Short: É um simples algoritmo de ordenação por inserção, que percorre um vetor, da esquerda para a direita, deixando os elementos da´ esquerda ordenados, funciona da maneira como se ordena cartas em um jogo de baralho. Esse ´e um bom método para ser aplicado em ordenação de arquivos pequenos, e arquivos quase ordenados.
• Shell Short: Proposto por Donald Shell em 1959, é a extensão do algoritmo de ordenação por inserção, pois ele tem uma ”melhora “em relação ao Insertion Short, pois, o InsertionSort, percorre o vetor, e troca apenas os itens ”vizinhos”, enquanto o ShellSort resolve esse problema, fazendo com que seja possível trocar itens distantes uns dos outros. E um método excelente para arquivos de tamanho moderado.
• Merge Short:´e um m´etodo criado em 1945, por John Von Neumann, e tem como caracter´ıstica a divisa˜o e conquista, no qual, ele divide o problema em problema menores, até resolv1ˆe-los, e depois de resolvidos, faz-se a uni˜ao das resoluc¸˜oes dos subproblemas. Por apresentar recursividade ´e um m´etodo que Utiliza muito espa¸co de memoria.
• Quick Short: ´e um m´etodo escrito em 1960 e publicado em 1962 ap´os alguns melhoramentos porCharles Antony Richard Hoare, ´e o algoritmo de ordenação interna mais ra´pido que se conhece. Ele utiliza-se conquista e divis˜ao, ao contra´rio do MergeSort, utilizando-se também da recursividade, e atrav´es desse m´etodo, se divide o vetor em dois, e se escolhe um item, chamado pivˆo, e os nu´meros menores ou igual ao pivoˆ ficam a esquerda e os maiores que pivoˆ ficam-se a direita.
• Heap Short: ´e um m´etodo criado por Robert W. Floyd e J.W.J. Williams, em 1964, ele se baseia no mesmo principio do SelectionSort, não utiliza memória adicional já´ que não se faz uso de recursividade, porem não ´e recomend´avel para arquivos pequenos com poucos registros, pois o tempo gasto na construc¸˜ao do Heap ´e um pouco grande.
• Radix Short: ´e um dos algoritmos de classifica¸ca˜o lineares. Funciona por triagem os nu´meros de entrada de cada d´ıgito, para cada um dos d´ıgitos no dado. No entanto,

o processo adotado por este m´etodo de classificac¸˜ao ´e um tanto contra-intuitiva, no sentido em que os nu´meros são classificados no d´ıgito menos significativo em primeiro lugar, seguido pelo segundo d´ıgito menos significativo e assim por diante até o algarismo mais significativo.

2. Estudo da Arte

Ao executar uma ordena¸˜ao, o processamento ´e influenciado pela quantidade de informa¸co˜es a serem processadas, e a arquitetura do hardware do computador que executara´ o determinado m´etodo.

Para ordenar um conjunto de dados de forma eficiente, existem diversos m´métodos de ordenação: Seleciona Short, Inserton Short, Shell Short, Merge Short, Quick Short, Radix Short, Bucket Short, Count Short, Cocktail Short, Heap Short.

Os m´métodos utilizados para estudo de caso sera˜o os seguintes:

• Seleciona Short
• Insertion Short
• Shell Short
• Merge Short
• Quick Short
• Heap Short

• Radix Short

2.1. Descri¸c˜ao dos m´métodos

2.1.1. Seleciona Short

E uma t´ecnica de ordenação que consiste em organizar uma determinada lista de dados´ atrav´es de dois la¸cos de repeti¸ca˜o aninhados, para possibilitar a compara¸c˜ao de cada item da lista com todos os outros itens. A ordenação ´e realizada comparando o item da posição inicial com todos os outros itens da lista que ainda não foram ordenados. O pr´oximo passo ´e comparar o item da segunda posição e compara´-lo com os demais valores da lista, e caso encontre um valor menor, a troca ´e realizada, o passo seguinte sera´ comparar o item da terceira posição com todos os outros itens seguintes e realizar a troca. Este processo ´e realizado diversas vezes enquanto o ponteiro não alcan¸car o u´ltimo item da lista. Caso não encontre um item menor, o item da posic¸˜ao inicial permanece na mesma posição e o ponteiro passa para a pro´xima posição.

...