Continuando a série: AED’s, irei mostrar agora, vários algoritmos para ordenação de dados em uma determinada coleção.

Conforme as publicações anteriores, farei a implementação em C#, caso queiram em alguma outra linguagem ou a explicação/implementação de algum algoritmo que não exista neste artigo, é só entrar em contato.

Mas primeiro (como de praxe), é importante perceber que apesar da complexidade ser mais elevada em alguns algoritmos, isto não os tornam melhores. Na verdade, são casos isolados de aplicação, e você analista/programador deverá decidir qual lhe servirá melhor.

Bubble Sort

O método de ordenação clássico. Não existem programadores que não ouviram falar dele. A ideia é percorrer a coleção diversas vezes, a cada passagem, colocando o elemento de menor ordem no início da coleção. Este algoritmo não é recomendado para a ordenação de coleções muito grandes.

Segue o código abaixo:

namespace ED
{
    public class SortMethods
    {
        public void BubbleSort (int[] colecao)
        {
            for (int i = colecao.Length - 1; i > 0; i--)
            {
                for (int j = 0; j < i; j++)
                {
                    if (colecao[j] > colecao[j + 1])
                    {
                        int swap = colecao[j];
                        colecao[j] = colecao[j + 1];
                        colecao[j + 1] = swap;
                    }
                }
            }
        }
    }
}

Selection Sort

A ordenação por seleção (selection sort), é um algoritmo de ordenação que sempre passa o valor de menor ordem para o início da coleção. Este algoritmo possui uma dependencia muito grande da disposição dos elementos da coleção para que seu desempenho seja ótimo. É considerado uma versão melhorada do Bubble Sort.

Segue o código abaixo:

namespace ED 
{ 
    public class SortMethods 
    { 
        public void SelectionSort (int[] colecao)
        {
            int index_min;
            int aux;

            for (int i = 0; i < colecao.Length; i++)
            {
                index_min = i;

                for (int j = i + 1; j < colecao.Length; j++)
                {
                    if (colecao[j] < colecao[index_min])
                        index_min = j;

                    if (index_min != i)
                    {
                        aux = colecao[index_min];
                        colecao[index_min] = colecao[j-1];
                        colecao[j-1] = aux;
                    }                
                }
            }
        }
    } 
}

Insertion Sort

Como o próprio nome diz, é uma ordenação por inserção. Eficiente quando aplicado a uma coleção de dados pequena (Assim como o Bubble Sort). Basicamente, percorre a coleção da esquerda para a direita, deixando os elementos mais à esquerda ordenados. Seu funcionamento é comparado ao modo como as pessoas (muitas delas) ordenam as cartas em um jogo de baralho.

Segue o código abaixo:

namespace ED 
{ 
    public class SortMethods 
    { 
        public void InsertionSort (int[] colecao) 
        { 
            for (int i = 0; i < colecao.Length; i++) 
            { 
                int aux = colecao[i]; 
                int j = i; 

                while (j > 0 && colecao[j - 1] > aux) 
                { 
                    colecao[j] = colecao[j - 1]; 
                    j = j - 1; 
                } 

                colecao[j] = aux; 
            } 
        } 
    } 
} 

Shell Sort

Este algoritmo passa várias vezes pela coleção, dividindo o grupo maior em menores. Nos grupos menores é aplicado o Insertion Sort. Dentre todos os métodos passados até agora, é considerado o mais eficiente.

Segue o código abaixo:

namespace ED 
{ 
    public class SortMethods 
    { 
        public void ShellSort (int[] colecao)
        {  
            int i, j, h = 1, swap;

            do
            {
                h = 3 * h + 1;
            }
            while (h < colecao.Length);

            do
            {
                h /= 3;

                // Neste ponto, é executado o Insertion Sort (leve variação)
                for (i = h; i < colecao.Length; i++)
                {
                    swap = colecao[i];
                    j = i - h;

                    while (j >= 0 && swap < colecao[j])
                    {
                        colecao[j + h] = colecao[j];
                        j -= h;
                    }

                    colecao[j + h] = swap;
                }
            }
            while (h > 1);
        }
    } 
} 

Heap Sort

Este algoritmo utiliza uma estrutura chamada Heap (Organizada como Árvore Binária). Ele ordena os elementos à medida que os insere na Árvore Binária. Ao final, basta remover os elementos da Árvore Binária (Usando o algoritmo InOrder) que estarão na ordem desejada. Possui um ótimo desempenho para coleções de dados ordenados aleatoriamente. Este é o algoritmo com desempenho bom/médio em em todos os casos.

Segue o código abaixo:

namespace ED 
{ 
    public class SortMethods 
    { 
        public void HeapSort (int[] colecao)
        {  
            this.HeapSort_BuildMaxHeap(colecao);
            int n = colecao.Length;

            for (int i = colecao.Length - 1; i > 0; i--) 
            { 
                this.HeapSort_Swap(colecao, i , 0);
                this.HeapSort_MaxHeapify(colecao, 0, --n);
            }
        }

        private void HeapSort_BuildMaxHeap (int[] colecao)
        { 
            for (int i = (colecao.Length / 2) - 1; i >= 0; i--)
                this.HeapSort_MaxHeapify(colecao, i , colecao.Length);
        }

        private void HeapSort_MaxHeapify (int[] colecao, int pos, int n) 
        { 
            int max = 2 * pos + 1, right = max + 1;

            if (max < n)
            { 
                if ( right < n && colecao[max] < colecao[right])
                    max = right;

                if (colecao[max] > colecao[pos]) 
                { 
                    this.HeapSort_Swap(colecao, max, pos);
                    this.HeapSort_MaxHeapify(colecao, max, n);
                }
            }
        }

        private void HeapSort_Swap (int[] colecao, int j, int aposJ)
        {
            int aux = 0;
            aux = colecao[j];
            colecao[j] = colecao[aposJ];
            colecao[aposJ] = aux;
        }
    } 
} 

Quick Sort

É considerado o algoritmo mais eficiente que existe (Média de desempenho em todos os casos). Lendário como o algoritmo mágico de ordenação, ele usa a estratégia de Dividir Para Conquistar. O algoritmo basicamente divide uma coleção (ou parte dela) em duas partes, a da esquerda possui os menores elementos de menor ordem, enquanto a da direita possui os maiores de maior ordem. Este processo é aplicado recursivamente nas partes até que toda a coleção esteja ordenada. O pior caso para este algoritmo é quando a coleção já está mais ou menos ordenada (que utopia não?).

Segue o código abaixo:

namespace ED 
{ 
    public class SortMethods 
    { 
        public void QuickSort(int[] colecao, int left, int right)
        {
            int lHold = left;
            int rHold = right;
            Random ObjRan = new Random();
            int pivot = ObjRan.Next(left, right);

            this.QuickSort_Swap(colecao, pivot, left);
            pivot = left;
            left++;

            while (right >= left)
            {
                if (colecao[left] >= colecao[pivot] && colecao[right] < colecao[pivot])
                    this.QuickSort_Swap(colecao, left, right);
                else if (colecao[left] >= colecao[pivot])
                    right--;
                else if (colecao[right] < colecao[pivot])
                    left++;
                else
                {
                    right--;
                    left++;
                }
            }

            this.QuickSort_Swap(colecao, pivot, right);
            pivot = right;

            if (pivot > lHold)
                this.QuickSort(colecao, lHold, pivot);

            if (RHold > pivot+1)
                this.QuickSort(colecao, pivot+1, rHold);
        }

        private void QuickSort_Swap(int[] colecao, int left, int right)
        {
            int swap = colecao[left];
            colecao[left] = colecao[right];
            colecao[right] = swap;
        }
    } 
} 

Então é isto. Nos próximos artigos da série ED’s, vou providenciar assuntos relacionados às metodologias de pesquisa. Até lá!