Ordenação Genérica em C

Introdução

Em um artigo anterior, tratei do problema da construção de estruturas de dados genéricas, isto é, estruturas capazes de manipular diferentes tipos de dados, informados no momento da criação destas estruturas. No final deste artigo, levantei a seguinte questão:

Como podemos criar uma função comparar os itens de uma estrutura de dados genérica, uma vez que ela não conhece o seu tipo, a priori. Mesmo sabendo qual é o tipo de dado, em alguns casos, não seria possível compará-los; por exemplo, quando o tipo de dado é uma estrutura complexa, criada pelo próprio desenvolvedor, como uma struct para armazenar os dados de um aluno, entre outros.

Para resolver este problema, utilizando a linguagem C, precisamos lançar mão de um recurso conhecido como funções callback. Esse tipo de função tira proveito do fato de que a linguagem C trabalha com ponteiros para funções, isto é, podemos passar para uma função, um ponteiro que aponta para o bloco da memória onde está localizada outra função do sistema (ou até mesmo a própria função que está recebendo o parâmetro). Isto permite que uma determinada função chame outras funções, mesmo sem ter conhecimentos de quais funções são estas.

Neste artigo, pretendo trabalhar com a questão das funções callback, envolvendo um assunto bastante explorado nas disciplinas de algoritmos e estruturas de dados, a saber, a ordenação. Ordenar é o processo de rearranjar um conjunto de objetos em uma ordem ascendente ou descendente. A ordenação visa a facilitar a recuperação posterior de itens do conjunto ordenado. Imagine, por exemplo, utilizar um catálogo telefônico, no qual os nomes das pessoas não estão organizados em ordem alfabética. Ou então utilizar um dicionário, no qual as palavras não estão listadas em ordem alfabética.

A maioria dos métodos de ordenação é baseada em comparação de chaves. Qualquer tipo de chave sobre o qual exista uma regra de comparação bem definida pode ser utilizado. De modo análogo ao que foi comentado no nosso artigo anterior, quando cursamos disciplinas de Algoritmos e Estruturas de Dados nos cursos de computação e áreas afins, em geral, aprendemos a implementar algoritmos de ordenação capazes de trabalharem apenas com números inteiros. Isto não é essencialmente um problema, uma vez que o intuito destas disciplinas é apresentar os principais tipos de algoritmos, suas aplicações e complexidades de tempo e espaço.

Contudo, quando vamos para a prática do desenvolvimento, ao utilizarmos estes algoritmos, sejam em um trabalho prático da disciplina ou em outro tipo de situação, nosso desejo será trabalhar com implementações capazes de ordenar qualquer tipo de elemento e não apenas de números inteiros.

Neste sentido, este artigo tem como objetivo apresentar o desenvolvimento de um algoritmo de ordenação simples, o Selection Sort (ordenação por seleção) de forma genérica, isto é, de forma que ela seja capaz de ordenar qualquer tipo de elemento especificado pelo usuário, sem exigir que seu código seja modificado.

O algoritmo de ordenação Selection Sort

Selection Sort (ou ordenação por seleção) é um dos algoritmos de ordenação mais simples. O pseudocódigo desse algoritmo pode ser descrito da seguinte forma:

  1. Selecione o menor elemento do vetor;
  2. Troque-o com o elemento da posição do início do vetor (após isto a posição de início apontará para a próxima posição do vetor);
  3. Repita essas duas operações com os n − 1 elementos restantes, depois com os n − 2 elementos, até que reste apenas um elemento.

A Figura 1 ilustra o funcionamento do método de ordenação Selection Sort, segundo descrito anteriormente.

Ordenação Genérica: ilustração do funcionamento do método de ordenação por seleção

Figura 1: Ilustração do funcionamento do método de ordenação por seleção.

Analogamente, sua implementação na linguagem de programação C é bastante simples, conforme é apresentado na seguinte listagem.

void ordenacaoPorSelecao(int vetor[], int n) {
   for(int i = 0; i < n - 1; i++) {
      int menor = i;
      for(int j = i + 1; j < n; j++) {
         if (vetor[j] < vetor[menor]) menor = j;
      }
      int aux = vetor[i];
      vetor[i] = vetor[menor];
      vetor[menor] = aux;
   }
}

O comando for mais interno deste algoritmo, linhas 4 à 6, é responsável por encontrar o menor elemento do vetor, cujos índices vão de i + 1 a n – 1. As linhas 7 à 9 são responsáveis por colocar o menor elemento identificado pelo for mais interno em sua posição correta. O comando for mais externo é responsável por percorrer todo o vetor, permitindo que todos os elementos sejam colocados no lugar certo. O valor da variável i deste comando representa a posição atual onde o menor elemento deverá ser colocado.

A análise da complexidade deste algoritmo, em função do número de comparações realizadas pelo mesmo, também é bem simples. Imagine um vetor de N elementos. Na primeira execução, o comando if será executado N – 1 vezes. Na segunda, N – 2. Na terceira, N – 3 e, assim sucessivamente, até a N-ésima – 1 vez, na qual o comando if será executado apenas 1 vez. Portanto, o número de comparações, C(n), realizada por este algoritmo é dado por:

C(n) = 1 + 2 + 3 + … + N -1

C(n) = [(N-1) * (N – 1 + 1)]/2
C(n) = (N2 – N)/2

Resumindo, em termos do número de comparações, este algoritmo é da classe quadrática, O(n2), de complexidade de tempo. Quanto ao número de movimentações realizadas pelo algoritmo, a análise é mais simples ainda. Ao executar o algoritmo passo a passo é possível observar que ele sempre irá realizar N – 1 movimentações para um vetor de tamanho N. Ou seja, em termos da quantidade de movimentações realizadas pelo algoritmo, Selection Sort é da classe de complexidade linear: O(n). Este é um resultado interessante para o número de movimentações, se comparado a outros algoritmos de ordenação, como o Bubble Sort ou o Insertion Sort, em seus piores casos.

Outra característica interessante deste algoritmo de ordenação é que o mesmo apresenta a mesma complexidade, qualquer que seja a configuração do vetor de entrada. Isto é, dado um vetor de tamanho N, não importa se o vetor está parcialmente ou totalmente ordenado, ou se está ordenado inversamente, a quantidade de comparações e movimentações a serem realizadas será sempre a mesma. Diferentemente de outros métodos de ordenação, que são sensíveis à configuração da entrada, como por exemplo o Insertion Sort, que apresenta um número de comparações bem menor quanto o vetor está totalmente ou parcialmente ordenado.

Outro ponto que chama a atenção no código da listagem anterior é que a função ordenacaoPorSelecao recebe como parâmetro um vetor de números inteiros e um inteiro que representa o tamanho deste vetor. O fato de ela receber um vetor de inteiros em sua definição, a impede de trabalhar com conjuntos referentes a outros tipos de dados, como strings ou até mesmo tipos complexos, como registros de “Alunos”, “Notas”, “Processos”, entre outros.

A questão chave é: o algoritmo de ordenação tem como responsabilidade colocar em ordem crescente ou decrescente um conjunto de registros, cujas chaves possam ser comparadas de alguma maneira. A priori, não é responsabilidade do algoritmo de ordenação saber como comparar dois registros de um conjunto de dados. Isso está relacionado ao domínio do problema que está sendo resolvido com o algoritmo de ordenação. Neste sentido, vamos aprender a criar um algoritmo de ordenação genérico, isto é, que seja capaz de ordenar qualquer conjunto de dados, sem se preocupar com o tipo destes dados.

Publicado na edição 48 (PDF) da Revista PROGRAMAR.