Combinando Algoritmos de Ordenação - Selection Sort e Merge Sort

Algoritmos de ordenação são fundamentais para uma série de processos computacionais utilizados cotidianamente pela sociedade, e é de igual importância que saibamos em quais condições uns são mais adequados do que outros para o melhor tratamento dos dados. O presente artigo expõe um estudo a respeito dos algoritmos ’selection sort’ e ‘merge sort’, procurando relacionar suas especificidades e custos computacionais.

Os processos de ordenação “selection sort” e “merge sort” compõem o conjunto básico de algoritmos que têm por finalidade a ordenação de dados. Ambos foram tomados como objeto de estudo para a análise de custo de algoritmos.

A análise de custos de algoritmos é feita de maneira ampla e diversificada de acordo com cada aplicação. Tomam-se parâmetros de medição como tempo de execução, tempo do processador, número de acessos à memória, atribuições, trocas, passagem de parâmetros, comparações e outros.

O Selection Sort possui complexidade quadrática por possuir duas instâncias de percorrimento da lista de dados: uma que permanece sobre o limiar da porção ordenada e desordenada do vetor, e outra que percorre a porção desordenada em busca do menor ou maior valor, dependendo do sentido da ordenação.

Já o Merge Sort possui complexidade logarítmica , e faz parte de um grupo de algoritmos do tipo “dividir para conquistar”, dividindo a sequência original em pares de dados ordenados, e depois juntando-os.

Utilizou-se a linguagem C e o compilador GCC para implementação dos dois algoritmos e do gerador de números aleatórios do kernel do Unix através do Bash. Este último gerou a sequência de números aleatórios submetidos à um arquivo de entrada lido pelo programa e ordenado pelos dois algoritmos.

for i in {1..1000000}; do
    echo $RANDOM;
done > teste.in

O custo foi computado através do incremento de variáveis de acordo com o número de interações de cada algoritmo, o que no caso da versão interativa do Selection Sort é o número total de comparações. O Merge Sort teve seu custo contado a cada chamada recursiva de intercalamento.

Custo analítico do Merge Sort:

Custo analítico do Selection Sort:

Com as descrições das complexidades dos algoritmos (quadrádica e logarítmica) das fórmulas 1 e 2, pode-se verificar que em algum momento haverá um cruzamento dos custos, pois um tenderá ao crescimento de custo muito rapidamente, enquanto o outro terá um crescimento linear.

O objetivo aqui seria verificar em que ponto um algoritmo torna-se mais custoso do que outro.
Com alguns procedimentos de ordenação chegou-se os seguintes valores que parecem ser suficientes para expor os resultados:

Referenciando-se aos custos dos algoritmos pode-se traçar o seguinte gráfico.

Para fins de confirmação, gerou-se um arquivo com 106 números aleatório, o qual foi submetido à ordenação somente pelo Merge Sort, e em outra instância pelo algoritmo combinado juntamente com o comando time do Unix.

O custo de cerca de seis a sete elementos de um vetor passa a ser maior em um algoritmo de seleção do que em um algoritmo de mistura. Por tais motivos pode-se construir um algoritmo combinado a fim de verificar o tamanho do fragmento de dados que o Merge Sort gera, e se este fragmento é maior ou melhor do que o limiar de custo entre os dois algoritmos.

Desta maneira, em uma larga ordenação o custo dos fragmentos menores do que sete elementos podem ser ordenados com o Selection Sort para alguma economia de processamento.

Modo de uso do algoritmo:

Os arquivos teste.in e teste.out são listas de inteiros, um por linha, respectivamente desordenadas e ordenadas.

./programa < teste.in > teste.out

Código Final:

# include <stdio.h>
# include <stdlib.h>
# include <time.h>
# include <string.h>
 
// @brief Imprime um vetor com um elemento por linha
// @param v Vetor a ser ordenado
// @param tam Tamanho do vetor a ser ordenado
void ImprimirVetor(int *v,int tam) {
        int i;
        for (i = 0; i < tam; i++) printf("%d\n",v[i]);
}
 
// @brief Intercala blocos de elementos do Merge Sort
// @param v Vetor a ser ordenado
// @param tam Tamanho do vetor a ser ordenado
void Intercala(int *v, int tam) {
        int meio;
        int i, j, k;
        int</em> tmp;
        tmp = (int*) malloc(tam * sizeof(int));
        if (tmp == NULL) exit(1);
        meio = tam / 2;
        i = 0;
        j = meio;
        k = 0;
        while (i < meio && j < tam) {
                if (v[i] < v[j]) {
                        tmp[k] = v[i];
                        ++i;
                } else {
                        tmp[k] = v[j];
                        ++j;
                }
                ++k;
        }
        if (i == meio) {
                while (j < tam) {
                        tmp[k] = v[j];
                        ++j;
                        ++k;
                }
        } else {
                while (i < meio) {
                        tmp[k] = v[i];
                        ++i;
                        ++k;
                }
        }
        for (i = 0; i < tam; ++i) {
                v[i] = tmp[i];
        }
        free(tmp);
}
 
// @brief Ordena um vetor pelo método de seleção
// @param v Vetor a ser ordenado
// @param tam Tamanho do vetor a ser ordenado
void SelectionSort(int *v, int tam) {
        int i, j, min, aux;
        for(i=0; i<tam-1; i++) {
                min = i;
                aux = v[i];
                for(j=i+1; j<tam; j++) {
                        if (v[j] < aux) {
                                min=j;
                                aux=v[j];
                        }
                }
                aux = v[i];
                v[i] = v[min];
                v[min] = aux;
        }
}
 
// @brief Ordena um vetor pelo método de mistura
// @param v Vetor a ser ordenado
// @param tam Tamanho do vetor a ser ordenado
void MergeSort(int *v, int tam) {
        int meio;
        if (tam >= 7) {
                meio = tam / 2;
                MergeSort(v, meio);
                MergeSort(v + meio, tam - meio);
                Intercala(v, tam);
        } else {
                SelectionSort(v,tam);
        }
}
 
int main() {
        int vtam, i = 1;
        int *v;
        v = malloc (i + sizeof(int));
        v[0] = 0;
        while (scanf("%d",&v[i-1]) != EOF) {
                ++i;
                v = (int*) realloc(v, i * sizeof(int));
        }
        --i; --i;
        vtam = i;
        MergeSort(v,vtam);
        ImprimirVetor(v,vtam);
        return 0;
}

Referências:
CORMEN, T.H.; CHARLES, E.L.; RONALD, L.R; CLIFFORD S. Algoritmos Teoria e Pratica. Editora Campus, 2000
MUSSER, David - Measuring Computing Times and Operation Counts of Generic Algorithms. Acessado em 21/10/09
REBELSKY, Samuel – MergeSort – Fundamentals of CSc. Acessado em 19/10/09
SZWARCFITER, J.L.; MARKENZON, . Estruturas de Dados e seus Algoritmos. LTC-Livros Técnicos e Científicos, Rio de Janeiro, RJ, 1994.
WIKIPEDIA. Merge Sort. Acessado em 23/10/09
WIKIPEDIA. Selection Sort. Acessado em 23/10/09