APS Unip Métodos de Ordenação Ciência da Computação

UNIVERSIDADE PAULISTA

Danillo de Oliveira Medeiros Martins

[pic 1]

Métodos de Ordenação:

Comparativo entre os métodos mais comuns

SÃO PAULO

2015

---

[pic 2]Sumário

1. Introdução............................................................................................................................03

2. Utilização de ordenação.......................................................................................................04

[pic 3]3. Métodos Selecionados..........................................................................................................05

4. Código fonte.........................................................................................................................06

 4.1. Bubble Sort........................................................................................................................06

 4.2. Insertion Sort.....................................................................................................................06

 4.3 Selection Sort......................................................................................................................07

5. Resultados dos testes............................................................................................................08

 5.1. Bubble Sort........................................................................................................................09

 5.2. Insertion Sort.....................................................................................................................10

 5.3 Selection Sort......................................................................................................................11

6. Conclusão.............................................................................................................................12

---

[pic 4]1. Introdução

        O presente comparativo tem por intuito realizar testes de performance de três dentre os mais comuns métodos de ordenação de vetores utilizados na computação pela linguagem de programação estrutura, sendo aqui utilizada a linguagem “C” como base dos testes.

---

[pic 5]2. Utilização de Ordenação

        A ordenação de vetores traz consigo a premissa de permitir mais facilmente a localização de itens dentro de um vetor ou matriz no âmbito computacional.

        Sendo utilizado principalmente para agilizar e facilitar a busca de itens dentro de um vetor. Permitindo através deste, inclusive, a busca binária que consiste em dividir o vetor em duas partes, desprezando a parte que não contêm o item buscado, essa operação é repetida n vezes até que reste somente o item buscado em si.

        Tal método de busca se torna inaplicável caso o vetor ou matriz não esteja ordenado, pois assim a execução de um programa de busca não teria condições de identificar a possível posição do elemento buscado, salvo caso o mesmo estivesse indexado, situação esta que dispensaria a ordenação, porém necessitando de maior espaço em memória para que fosse criado o índice.

---

[pic 6]3. Métodos Selecionados

        Dentre os diversos métodos conhecidos para a ordenação de vetores foram selecionados três dentre os mais comuns para a comparação de performance que consiste em analisar a praticidade de implantação do algoritmo em um programa, a sua facilidade de utilização e a sua velocidade de execução em relação ao tamanho do vetor.

        Sendo para este teste selecionados os métodos conhecidos como: “Bubble Sort” (ordenação bolha), “Insertion Sort” (ordenação de inserção) e “Selection Sort” (ordenação de seleção).

        Apesar de serem vastamente conhecidos, computacionalmente, faremos aqui uma breve descrição de cada para melhor entender a lógica do algoritmo.

        Bubble Sort: este método simples de ordenação tem como preceito percorrer o mesmo vetor diversas vezes e reorganiza-lo de modo que os elementos de menor valor sejam colocados nas primeiras posições.

        Insertion Sort: esse algoritmo percorre um vetor de elementos da esquerda para a direita e à medida que avança vai deixando os elementos mais à esquerda ordenados.

        Selection Sort: baseado em passar sempre o menor valor do vetor para a primeira posição, depois o de segundo menor valor para a segunda posição, e assim é feito sucessivamente com os elementos restantes, até os últimos dois elementos.

---

4. Código fonte

Para facilitar a compreensão e melhor demonstrar a implementação do algoritmo, será disponibilizado o ponto central do mesmo para conhecimento, sendo representado o tamanho do vetor pela palavra “SIZE”.

4.1 Bubble Sort:

for (x=0;x

        {

                for (y=x+1;y

                {

                        if(vector[x]>vector[y])

                        {

                                temp=vector[x];

                                vector[x]=vector[y];

                                vector[y]=temp;

                        }

                }

        }

[pic 7]4.2. Insertion Sort:

for (x=1;x

        {

                temp=vector[x];

                y=(x-1);

                while((y>0)&&(vector[y]>temp))

                {

                        vector[y+1]=vector[y];