APS - Ordenação de Dados

...

3 - Introdução

Em vários momentos do nosso cotidiano, todos nós nos deparamos com dados ordenados, ou seja, com informações que foram classificadas seguindo uma ordem pré-estabelecida, com a finalidade de facilitar a consulta desses dados. Um exemplo de dados ordenados é a lista telefônica, imagine como seria demorado e complicado encontrar uma pessoa nessa lista se os nomes não estivem em ordem alfabética. Podemos citar também uma situação em que precisamos organizar várias faturas para podermos pagá-las na ordem de vencimento, para isso, normalmente nós classificamos as contas conforme sua data de vencimento, assim estamos ordenando esses dados, buscando facilidade e praticidade para otimizar nosso tempo que está cada vez mais escasso.

Na computação existem algoritmos que são construídos para organizar informações, esses algoritmos são chamados de métodos para ordenação de dados e são muito usados em todas as esferas da informática. Explicando de uma maneira mais simplista, esses algoritmos se encarregam de rearranjar um conjunto de objetos que foram inseridos na entrada do programa computacional, como números e/ou letras, para que na saída do programa seja mostrado esses objetos na ordem escolhida, podendo ser na ordem ascendente ou descendente. Os dados mais comumente utilizados na entrada de um programa para ordenação são os numéricos e os lexicográficos (caracteres).

Os métodos de ordenação de dados são classificados em dois grandes grupos: ordenação interna e externa. Na ordenação interna, os métodos não precisam de uma memória secundária para o processo, a ordenação é feita na memória principal do computador. A ordenação externa ocorre quando os dados a serem ordenados não cabem na memória principal, por isso, precisam ser armazenados em disco ou fita. A principal diferença entre esses dois grandes grupos é que no método de ordenação interna, qualquer registro pode ser acessado diretamente, enquanto no método de ordenação externa é necessário fazer o acesso em blocos.

No momento, os métodos de ordenação de dados mais populares são: Insertion sort, Selection sort, Bubble sort, Comb sort, Quick sort, Merge sort, Heap sort e Shell sort.

Nesse trabalho acadêmico será abordado e explicado dois métodos de ordenação mais simples conhecidos como Insertion sort e Selection sort, e um método considerado mais sofisticado, o Quick sort, explicando minuciosamente cada um deles e mostrando o passo a passo do processo de construção dos seus algoritmos. Nesse trabalho também será mostrado um comparativo entre os três métodos escolhidos, usando como entrada, dados de um vetor pré-estabelecido, visando informar ao leitor qual método possui melhor performance de resultado, analisando o número de comparações entre chaves do vetor, o número de linhas de comando processadas para a ordenação e a contagem de tempo gasto durante a execução do algoritmo.

Ao final desse trabalho será apresentado um código fonte em C# com o algoritmo dos três métodos de ordenação escolhidos: Insertion sort, Selection sort e Quick sort, para, caso o leitor queira, poder confirmar ou acompanhar os resultados obtidos.

Boa leitura.

4 - Insertion Sort.

4.1 - Referencial Teórico

O Insertion Sort é um método simples de ordenação no qual é responsável por organizar elementos em ordem crescente a partir da esquerda de um arranjo, que irá comparar 2 elementos em uma região do vetor que não esteja ordenado. A inserção do elemento em uma posição adequada na sequência de destino é realizada com a movimentação de valores maiores para a direita e então é feita a inserção do elemento na posição vazia. Se o elemento selecionado for menor que o anterior, este será trocado de posição com o antecessor, formando um sub-arranjo. Este processo de comparação será feito até que o vetor, ou arranjo, esteja corretamente ordenado e o vetor seja totalmente percorrido. Este método é parecido com a forma de organização de cartas feita por jogadores de cartas, como no pôquer, por exemplo.

Dessa forma, este método possui fácil entendimento, implementação ou ainda eficiência quando houver poucos dados e quando o vetor estiver parcialmente ordenado. O método também é classificado como estável, pois os registros com chaves iguais sempre irão manter a mesma posição relativa de antes do início da ordenação.

Ao contrário do que foi citado anteriormente, se houver uma situação onde o vetor possua vários elementos não ordenados, este método não será eficiente, do mesmo modo quando o vetor estiver inversamente ordenado, pois será necessário realizar todo o processo de comparação entre 2 elementos por vez e a obtenção dos resultados será demorada, gerando um grande número de movimentações de elementos.

A seguir, iremos exemplificar detalhadamente todo o processo do método em questão, com arranjos parcialmente ordenados e inversamente ordenados através de figuras representando um vetor e números, e posteriormente iremos implementar um código em C# que irá mostrar a relação de tempo com a quantidade de elementos dentro de um vetor.

4.2 - Desenvolvimento

A figura abaixo mostra um exemplo de um vetor não ordenado no qual será utilizado o método Insertion Sort parcialmente ordenado classificado como melhor caso:

[pic 2]

O algoritmo irá fazer a comparação dos dois primeiros números (posição 0 e 1). A regra adotada por ele é de que sempre o segundo número deve ser maior do que o primeiro. Se entrar em condição falsa, ambos serão trocados de posição e será feito a varredura do vetor até que todos os elementos sejam ordenados.

Sendo 5 maior do que 2, o programa irá dar continuidade ao próximo elemento.Com condição de que o número 1 não é maior do que 5, consequentemente ambos serão trocados de posição, onde o número 1 irá assumir a posição 1 e o número 5 irá assumir a posição 2.Dessa forma, o vetor terá valores alterados conforme figura abaixo:

[pic 3]

Podemos perceber na figura que o número 1 da posição 1 não é maior do que o número 2 da posição 0, onde será necessário a troca de ambos. Dessa forma o número 1 irá assumir a posição 0 e o número 2 irá assumir a posição 1:

[pic 4]

Posteriormente, o algoritmo irá comparar os valores a partir