OS ALGORITMO DE ORDENAÇÃO

1 Introdução e Objetivo

Ordenação é o processo de arranjar um conjunto de informações semelhantes em uma ordem crescente ou decrescente. Tal processo, está presente na maioria das aplicações em que objetos e informações armazenados precisam ser pesquisados e recuperados.

Sua principal função é facilitar a recuperação posterior de itens do conjunto ordenado. Um exemplo, seria um catálogo telefônico. Sem a ordenação dos nomes das pessoas em ordem alfabética, seria muito difícil utiliza-lo. Assim, evidencia-se que a utilização de dados ordenados é inquestionável.

Alguns algoritmos podem explorar a ordenação dos dados para operar de maneira mais eficiente, do ponto de vista de desempenho computacional. Para obtermos os dados ordenados, temos basicamente duas alternativas: ou inserimos os elementos na estrutura de dados respeitando a ordenação (dizemos que a ordenação é garantida por construção), ou, a partir de um conjunto de dados já criado, aplicamos um algoritmo para ordenar seus elementos (W.CELES e J.L.RANGEL,2002).

Existem vários algoritmos que fazem a ordenação de maneiras diferentes, possuindo vantagens e desvantagens as quais devem ser consideradas conforme a aplicação que se destinam. Para decidir qual método é o melhor, certos critérios de eficiência precisam ser estabelecidos, e um método para comparar diferentes algoritmos precisa ser selecionado.

Os métodos de ordenação são classificados através de sua complexidade (O) e são em geral, classificados em dois grandes grupos: métodos de ordenação interna (vetores) e métodos de ordenação externa (arquivos). Se o arquivo a ser ordenado é pequeno, ou seja, cabe todo na memória principal então o método ordenador é chamado de ordenação interna. Em um método de ordenação interna, qualquer registro pode ser imediatamente acessado. Se o arquivo a ser ordenado não cabe na memória principal e por isso tem de ser armazenado em fita ou disco, então o método de ordenação é chamado de ordenação externa. Em um método de ordenação externa, os registros são acessados sequencialmente ou em grandes blocos. Existem os métodos simples, que são ideais para conjuntos pequenos, requerem O(n2) comparações, produzem programas pequenos e fáceis de entender; e existem métodos eficientes que são adequados para conjuntos maiores, requerem O(n log n) comparações, usam menos comparações e essas comparações são mais complexas nos detalhes (VIANA,2016).

O objetivo desse trabalho consiste em estudar os algoritmos de ordenação de dados e toda teoria computacional envolvida. A unidade de medida para efeito de comparação do desempenho dos algoritmos escolhidos e implementados deverá ser o tempo total de ordenação, não contabilizando o tempo de aquisição dos dados, mas somente a ordenação em si. Os algoritmos escolhidos para implementação e comparação neste trabalho tratam-se do BubbleSort (método da bolha), do QuickSort (método da troca e partição), do InsertionSort (método da inserção direta) e do Merge Sort (método da intercalação), os quais, Bubble Sort e Quick Sort serão implementados na linguagem de programação JAVA.

O capítulo 2 consiste do referencial teórico. Após o referencial teórico, o capítulo 3 apresenta o desenvolvimento dos algoritmos escolhidos pelo grupo, depois no capítulo 4 os resultados e discussões, isto é, como foram aplicados os testes e sobre o desempenho obtido pelos algoritmos, etc. No capítulo 5 o grupo apresentará as considerações finais e o seu entendimento sobre tudo que foi feito. E finalmente as referências para esta pesquisa e o código dos algoritmos desenvolvidos como anexo.

2 Referencial Teórico

Este capítulo aborda a teoria envolvida na proposta deste trabalho.

2.1 Conceitos sobre Algoritmos de Ordenação

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 (ordem alfabética).

Existem várias razões para se ordenar uma sequência, uma delas é a possibilidade se acessar seus dados de modo mais eficiente. (MARCOS LAUREANO,2012).

Há vários algoritmos de ordenação, mas para este trabalho foram escolhidos para o estudo os algoritmos de ordenação: Bubble Sort, Quick Sort, Insertion Sort, Merge Sort. (DEVMEDIA,2012).

2.2 Algoritmo de ordenação por troca (BUBBLE SORT)

Neste algoritmo de ordenação serão efetuadas comparações entre os dados armazenados em um vetor de tamanho n. Cada elemento de posição “i” será comparado com o elemento de posição i+1, e quando a ordenação procurada (crescente ou decrescente) é encontrada uma troca de posições entre os elementos é feita. Assim, um laço com a quantidade de elementos do vetor será executado (for(j=1; j<=n; j++)), e dentro deste, um outro laço que percorre da primeira a penúltima posição do vetor (for(i=0; i<n-1; i++)). Na próxima página, o algoritmo de BUBBLE SORT será ilustrado, implementando e analisando com o objetivo de ordenar os dados de forma crescente.

A ilustração a seguir mostra a execução do algoritmo BUBBLE SORT na ordenação crescente de um vetor com 5 elementos

Fonte: Ana Fernanda G.A e Graziela Santos A. (2010)

Fonte: Ana Fernanda G.A e Graziela Santos A. (2010)

2.2.1 Análise de complexidade

O principal trecho de código do algoritmo BUBBLE SORT é aquele que a ordenação realmente é realizada. O trecho é mostrado a seguir.

Fonte: Ana Fernanda G.A e Graziela Santos A. (2010)

Em alguns algoritmos de ordenação o fator relevante que determina seu tempo de execução é o número de comparações realizadas. Considerando que o algoritmo foi complementado para um vetor de 5 posições, verifica-se que o número de iterações do primeiro laço é 5. O segundo laço possui 4 iterações, mas como está interno ao primeiro, este será executado 20 vezes (5x4). Logo, o número de comparações (condição SE) realizadas será 20.

Aplicando