Metodo De Ordenação

Métodos de ordenação na teoria e na pratica

André L. Moreira

Universidade Regional Integrada do Alto Uruguai e das Missões Campus Santiago (URI) – Santiago, RS – Brasil

andreewgms@gmail.com, andreluizmmoreira@gmail.com, richardjhilean@gmail.com

Abstract. Ordering is very important because it makes computing simple, fast and feasible location or recovery of any particular information on a large set of information. Think how it would be infeasible to find a particular song in a folder with more than a thousand items if those items were not ordered in any way. Thus this article aims to describe the ordering methods theoretical and practical algorithms addressing their main mode, so as to strengthen the theoretical knowledge with the description of each case and practical with codes attached example implementations of the C language the most important methods.

Keywords: Ordenation, Methods, Sort

Resumo. A ordenação é muito importante para computação pois torna mais simples, rápida e viável a localização ou a recuperação de uma determinada informação em um conjunto grande de informações. Pense como seria inviável encontrar uma determinada música em uma pasta com mais de mil itens se esses itens não estivessem de alguma maneira ordenados. Desta forma este artigo tem o objetivo de descrever os métodos de ordenação de modo teórico e prático abordando seus principais algoritmos, de maneira a fortalecer o conhecimento teórico com a descrição de cada caso e prático com códigos de exemplo em anexo de implementações em linguagem C dos mais importantes métodos.

Palavras chaves: Ordenação, Métodos, Sort

1. Introdução

Muitas vezes na programação é preciso organizar itens de uma lista para facilitar o seu acesso. Segundo D. Knuth (no terceiro volume de seu tratado “The Art of Computer Programming”), há estatísticas de que na década de 1960, 25% do processamento ocorrido em computadores consistia em tarefas de ordenação. Esse tipo de tarefa pode ser realizada por um ser humano de maneira intuitiva. Mas em um programa é preciso seguir uma sequência exata de instruções para ordenar uma lista, e essa sequência é chamada algoritmo. Um algoritmo de ordenação é um método utilizado para colocar uma lista de itens desorganizados em uma determinada ordem. Existem vários algoritmos de ordenação que diferem em termos de eficiência e desempenho. Neste artigo, será abordado esse assunto[6].

Algoritmo de ordenação em ciência da computação é um algoritmo que coloca os elementos de uma dada sequência em uma certa ordem, em outras palavras, efetua sua ordenação completa ou parcial. As ordens mais usadas são a numérica e a lexicográfica. Existem várias razões para se ordenar uma sequência, uma delas é a possibilidade se acessar seus dados de modo mais eficiente[8].

Desta forma os métodos de ordenação podem ser classificados em dois tipos de métodos: Ordenação interna onde o arquivo a ser ordenado cabe todo na memória principal e a Ordenação externa em que o arquivo a ser ordenado não cabe na memória principal. Assim a diferença entre estes tipos de métodos de ordenação consiste em que a ordenação interna pode acessar imediatamente qualquer registro, enquanto na ordenação externa, os registros são acessados sequencialmente ou em grandes blocos[6].

2. Ordenação interna

Ordenar uma sequência de dados é um dos procedimentos mais usados no processamento de dados. Para esta tarefa temos algoritmos simples, e algoritmos sofisticados, cada um deles possui características diferentes e se comportam de maneira distintas dependendo do tamanho da entrada[3].

Se a lista que deve ser ordenada não for muito grande ela pode ser armazenada na memória principal (interna) do computador e ser ordenada usando apenas a me memória interna. Assim cada elemento pode ser imediatamente acessado. Os algoritmos que ordenam utilizando apenas a memória interna são chamados de métodos de ordenação interna. Todo arquivo a ser ordenado cabe na memória RAM.

Os métodos de ordenação interna são classificados em dois subgrupos: os métodos simples e os métodos sofisticados (Tabela 1).

MÉTODOS SIMPLES MÉTODOS SOFISTICADOS

Adequados para pequenos arquivos. Adequados para grandes arquivos.

Programas pequenos e fáceis de implementar. Requer poucas comparações.

Problema: requer muitas comparações. Problema: complexo para se implementar.

Tabela 1. Comparação de métodos Simples e Sofisticados

Algoritmos considerados mais simples, tem o número de operações de (n2) no pior caso, onde n é o número de elementos do vetor. São Exemplos de métodos simples[3]:

1 - Insertion sort

2 - Selection sort

3 - Bubble sort

4 - Comb sort.

A seguir são apresentados os métodos de ordenação simples.

2.1. Bubble sort (Ordenação por bolha)

O Bubble sort, ou ordenação por bolha, é um método de ordenação simples, um dos mais fáceis de implementar. Consiste em percorrer o vetor várias vezes, a cada passagem fazendo flutuar para o topo o maior elemento da sequência utilizando pares de comparações e trocas.

A maior vantagem do método de ordenação por bolha é que sua implementação é fácil e conhecida. Além disso, no Bubble sort o requerimento de espaço é mínimo. Uma desvantagem é que não apresenta bons resultados quando a lista contém muitos itens. Isso porque esse tipo de ordenação exige n² passos de processamento onde n é o número de elementos que serão ordenados. Portanto, o Bubble sort é indicado para o ensino academio, mas não para aplicações na vida real.

A Figura 1 apresenta a implementação do método Bubble Sort em linguagem C.

Figura 1. Implementação do método Bubble Sort em C.

2.2. Insertion sort (Ordenação por inserção)

O Insertion sort, ou ordenação por inserção, é um método de ordenação simples, o método mais rápido entre os métodos simples. Consiste em ordenar um conjunto de elementos, utilizando um subconjunto ordenado localizado em seu início, e em cada interação, acrescentamos a este subconjunto mais um elemento, até que atingimos o último elemento do conjunto assim com que ele se torne ordenado. Assim sendo ele vai ordenando os valores do vetor da esquerda para a direita[8].

Uma das vantagens de se usar a ordenação por inserção é que ela ordena o vetor somente quando realmente necessário. Se o vetor já está em ordem, nenhum movimento substancial será realizado. O algoritmo reconhece que parte do vetor já está ordenado e para a execução. Mas ele reconhece apenas isso, e o fato de que elementos podem já estar em suas posições apropriadas não é explorado. Em consequência, eles podem ser movidos dessas posições e voltarem mais tarde. Outra desvantagem é que, se um item está sendo inserido, todos os elementos maiores do que ele têm que ser movidos[8].

A Figura 2 apresenta a implementação do método Insertion Sort em C.

Figura 2. Implementação do método Insertion sort em C.

2.3. Selection sort (Ordenação por seleção)

O Selection sort, ou ordenação por seleção, é um método de ordenação simples que procura o próximo menor valor da lista e coloca na posição atual e vai se deslocando para a direita até o fim do vetor.

A principal vantagem do Selection sort (Figura 3) é que ela funciona bem em uma lista pequena. Sua desvantagem é a baixa eficiência em listas grandes. Assim como o Bubble sort, ele exige n² números de passos para cada n elementos. Adicionalmente, o seu desempenho é facilmente influenciado pela ordem inicial dos itens antes do processo de triagem. Devido a isso, esse tipo seleção é adequado apenas para uma lista em que poucos elementos estejam em ordem aleatória[8].

O número de operações ainda é (n2). Parecido com o Bubble Sort, entretanto o número de swaps é bem menor sendo mais eficiente na maioria das situações[6].

Figura 3. Implementação do método Selection sort em C.

Algoritmos considerados mais sofisticados, tem o número de operações de (n log n) no pior caso, onde n é o número de elementos do vetor. São Exemplos de métodos sofisticados:

1 - Merge sort

2 - Heap sort

3 - Shell sort

4 - Gnome sort

5 - Count sort

6 - Bucket sort

7 - Cocktail sort

8 - Tim sort

9 - Quick sort

2.4. Merge sort (Ordenação por Mistura)

Merge sort é um algoritmo de ordenação recursivo muito simples e fácil de implementar. O método merge sort divide a lista em duas partes iguais, essas partes são novamente divididas e assim usando a recursividade cada parte é dividida em partes iguais até que fiquem apenas dois elementos, todos os pares são colocados em ordem, assim o método retorna unindo e ordenando os pares de elementos até que a lista fique completa de novo e totalmente ordenada. O tempo de execução não depende do estado de ordenação dos elementos da lista ou seja o método merge sort (Figura 4) faz sempre o mesmo número de operações independente de sua ordenação inicial [8].

Figura 4. Implementação do método Merge sort em C.

A ação de “dividir para conquistar” é feito em 3 passos: [3]

1. Dividir: Dividir os dados em subsequências pequenas.

2. Conquistar: Classificar as duas metades recursivamente aplicando o merge sort.

3. Combinar: Juntar as duas metades em um único conjunto já classificado.

2.5. Quick sort

O algoritmo Quick sort é um método de ordenação muito rápido e eficiente, inventado por Hoare em 1960. Foi publicado em 1962 após uma série de refinamentos. Ele seleciona um elemento aleatório como pivô e particiona o resto colocando os menores à esquerda e os maiores à direita. Faz se o mesmo com os elementos da esquerda e direita até não ser mais possível particioná-los, obtendo-se os elementos ordenados. Sua implementação pode ser estruturada ou recursiva. Onde a recursiva é mais custosa por fazer várias chamadas à mesma função e necessitar de uma pequena pilha como memória auxiliar. É um método não-estável e sua melhor eficiência depende da escolha do pivô, onde uma boa escolha pode variar de uma complexidade de O (n log n) a O(n2). Muito utilizado na prática, é o algoritmo mais rápido para ordenações em memória interna. Os passos do método são definidos abaixo:[6]

1. Dividir: rearranje a lista de forma que todos os elementos anteriores ao pivô sejam menores ou iguais a ele, e todos os elementos posteriores ao pivô sejam maiores ou iguais a ele. Ao fim do processo o pivô estará em sua posição final.

2. Conquistar: recursivamente ordene a sublista dos elementos menores e a sub- lista dos elementos maiores.

3. Combinar: junte as listas ordenadas e o pivô.

Figura 5. Implementação do método Quick sort em C.

2.6. Shell sort

Proposto por Donald Shell em 1959, é uma extensão do algoritmo de ordenação por inserção. O algoritmo difere do método de inserção direta pelo fato de no lugar de considerar o array a ser ordenado como um único segmento, ele considera vários segmentos sendo aplicado o método de inserção direta em cada um deles. Basicamente o algoritmo passa várias vezes pela lista dividindo o grupo maior em menores. Nos grupos menores é aplicado o método da ordenação por inserção[6].

Vantagens: Shell sort é uma ótima opção para arquivos de tamanho moderado. Sua implementação é simples e requer uma quantidade de código pequena (Figura 6).

Desvantagens: O tempo de execução do algoritmo é sensível à ordem inicial do arquivo. O método não é estável.

Figura 6. Implementação do método Shell sort em C.

3. Ordenação externa

A ordenação externa consiste ordenar arquivos de tamanho maior que a memória interna disponível.

“A ordenação externa envolve arquivos compostos por um número de registros que é maior do que a memória principal do computador pode armazenar. Os métodos de ordenação externa são muito diferentes dos métodos de ordenação interna. Em ambos os casos o problema é o mesmo: rearranjar os registros de um arquivo em ordem ascendente ou descendente. Entretanto, na ordenação externa as estruturas de dados têm que levar em conta o fato de que os dados estão armazenados em unidades de memória externa, são relativamente muito mais lentas do que a memória principal”. (Freire et al 2011).

Na ordenação externa os dados são armazenados como um arquivo sequencial na memória externa (HDs, CDs), onde apenas um registro pode ser acessado por vez. Se comparada com a ordenação interna, onde os dados estão disponíveis na memória principal (RAM), a ordenação externa vai gastar um tempo muito maior para acessar todos os arquivos, enquanto na ordenação interna os dados são acessados imediatamente. (NAZARÉ, 2008)

3.1 Diferenças entre ordenação externa e ordenação interna

Segundo (Freire et al 2011), existem três importantes fatores que fazem os algoritmos para ordenação externa diferentes dos algoritmos para ordenação interna, a saber:

1. O custo para acessar um item é algumas ordens de grandeza maior do que os custos de processamento na memória interna. O custo principal na ordenação externa está relacionado com o custo de transferir dados entre a memória interna e a memória externa.

2. Existem restrições severas de acesso aos dados. Por exemplo, os itens armazenados em fita magnética só podem ser acessados de forma sequencial. Os itens armazenados em disco magnético podem ser aces- sados diretamente, mas a um custo maior do que o custo para acessar sequencialmente, o que contraindica o uso do acesso direto.

3. O desenvolvimento de métodos de ordenação externa é muito de- pendente do estado atual da tecnologia. A grande variedade de tipos de unidades de memória externa pode tornar os métodos de ordenação externa dependentes de vários parâmetros que afetam seus desempenhos.

4. Conclusão

Com o desenvolvimento deste trabalho pode observar que para se obter o conhecimento mais abrangente sobre o conteúdo deve se desenvolver o estudo equilibrando entre a parte teórica e a parte pratica, pois uma complementa a outra. Ao longo do estudo sobre os métodos de ordenação o aprendizado foi mais compreendido com a implementação dos métodos abordados em linguagem C, pois o conteúdo pode ser visualizado melhor e o grupo possui mais afinidade e um melhor aprendizado sobre esta linguagem.

5. Referencias

[1] CORMEN, T. H. et al. “Algoritmos: Teoria e Prática”. Rio de Janeiro: Elsevier, 2002.

[2] SZWARCFITER, J. L. e MARKENZON, L. “Estruturas de dados e seus algoritmos”. LTC editora, 1994.

[3] WIRTH, N. “Algoritmos e Estruturas de Dados”. Rio de Janeiro: Prentice-Hall do Brasil, 1989. 68 p.

[4] BRANDÃO, C. e NOGUEIRA, F. “ORDENAÇÃO DE DADOS EM MEMÓRIA EXTERNA UTILIZANDO PROGRAMAÇÃO PARALELA”. Vila Velha, 2008. 68p.

[5] FREIRE L. P. M. et al, “Ordenação Externa: Intercalação Balanceada e Intercalação Polifásica”. Fortaleza, 2011 CE–Brasil: Universidade Estadual do Ceará (UECE).

[6] SOUZA, R. e RODRIGUES, H. “Algoritmos e Estrutura de Dados”. Recife: Universidade Federal Rural de Pernambuco, 2010. 123p.

[7] NAZARÉ, A. “ALGORITMOS E ESTRUTURAS DE DADOS Métodos de ordenação Interna”. Ouro Preto: Universidade Federal de Ouro Preto, 2008. 76p.

[8] LAUREANO, M. “Estrutura de Dados com Algoritmos e C”. Rio de Janeiro: Brasport, 2008. 176p.

[9] WIKIPEDIA. “Algoritmo de Ordenação”. Disponível em: <http://pt.wikipedia.org/wiki/ Algoritmo_de_ordena%C3%A7%C3%A3o>. Acesso em: 6 Jul. 2014.

[10] UNICAMP. “Ordenação”. Disponível em:< http://www.dca.fee.unicamp.br/cursos/EA876/ apostila/HTML/node22.html>. Acesso em: 5 Jul. 2014.

...