Algoritmia Clássica em C++

Breve Introdução Histórica

A linguagem C++ foi desenvolvida durante os anos 80 na Bell Labs, pelo cientista de computação dinamarquês Bjarne Stroustrup. Esta linguagem é muitas vezes retratada como uma evolução da linguagem C. De facto, esta linguagem foi a principal base de desenvolvimento de C++, tanto mais que a primeira versão da nova linguagem tinha o nome de C With Classes, evoluindo mais tarde para C++. Em português deve-se pronunciar “cê mais mais” sendo que em inglês esta linguagem é pronunciada como “cee plus plus”.

As vantagens introduzidas pelo C++ face ao C são indiscutíveis. No entanto, e muitas vezes devido ao facto de ser uma linguagem com facilidades de alto nível, ocorrem erros lógicos (os temidos bugs) difíceis de resolver e frequentemente com consequências trágicas para o computador que está a correr a aplicação. São por isso famosas as duas citações de Stroustrup acerca das “facilidades” da sua nova linguagem:

  • “C faz com que dar um tiro no pé seja fácil; C++ torna isso mais difícil, mas quando nós o fazemos rebenta com a perna toda.”
  • “Sempre desejei que o meu computador fosse tão fácil de usar como o meu telefone. O meu desejo realizou-se. Já não sei usar o meu telefone.”

Nem sempre é simples para iniciantes da linguagem ou programadores inexperientes evitar que estes erros aconteçam. É por esta razão que muitas vezes é recomendado um período de adaptação à sintaxe de C e desenvolvimento de aplicações nesta linguagem, antes de se dar o salto para o C++.

Algoritmos Clássicos – Ordenação

Existe um alargado conjunto de algoritmos informáticos que desempenham um papel quase vital no desenvolvimento de aplicações coerentes e sólidas. Estes algoritmos, conhecidos como algoritmos clássicos, são frequentemente usados como “sub-rotinas” em aplicações mais complexas.

Um grupo de algoritmos clássicos que apresenta um vasto domínio de aplicação é o dos algoritmos de ordenação. Este grupo de algoritmos apresenta variadas técnicas que possibilitam a ordenação dos elementos de um array segundo uma determinada lógica (pode-se proceder a uma ordenação de forma ascendente ou descendente).

Neste artigo serão apenas abordados dois dos muitos algoritmos de ordenação de arrays: o QuickSort (por muitos considerado o melhor algoritmo de ordenação) e o BubbleSort.

BubbleSort

O algoritmo BubbleSort é talvez o algoritmo mais simples de se perceber dentro do género. A sintaxe que este algoritmo apresenta não necessita de explicações exaustivas, visto recorrer a aspectos básicos de programação (ciclos for/while, comparação de diferentes elementos do array, incrementação de uma variável, etc.). O próprio funcionamento do BubbleSort é muito simples: por cada iteração do ciclo, o maior elemento do array (para um determinado intervalo de elementos desse mesmo array) é colocado no índice final, previamente estabelecido. Isto é conseguido à custa de sucessivas comparações de um elemento do array com o seu elemento seguinte.

O seguinte excerto de código ilustra a implementação do BubbleSort:

//função para trocar dois elementos do array (utilização de referências para afectação directa)
void swap (int& n1, int& n2)
{
  //guardar o valor de n2
  int aux = n2;
  //afectar n2 com o valor de n1
  n2 = n1;
  //afectar n1 com o valor de aux (valor inicial de n2)
  n1 = aux;
}
 
//a função recebe como argumentos o array a ordenar e o numero máximo de elementos a ordenar 
void bsort (int v[], int n)
{
  for (int i = n; i > 0; --i)  //ciclo responsável pelas decrementações do índice máximo 
  {
    for (int j = 0; j < i; ++j) //ciclo responsável por incrementar os índices a ordenar
    {
      if (v[j] > v[j+1]) //se um elemento é maior que o seu elemento seguinte
      {
         swap (v[j], v[j+1]); //chamar a função para trocar dois elementos do array
      }
    }
  }
}

O primeiro ciclo for é o responsável por decrementar o índice máximo para as ordenações. Assim, se se quiser ordenar um array tomando em conta todos os seus elementos, terá de se iniciar a variável que irá percorrer todos os índices com o valor do tamanho do array. Depois de serem efectuadas todas as operações uma primeira vez, tem-se a certeza que o maior elemento do array se encontra no índice final. Na segunda vez que se irão realizar as operações de ordenação, não interessa que se tenha em conta todo o array (se assim fosse estariam a ser feitas comparações desnecessária, ocupando recursos da máquina injustificadamente). Logo, decrementa-se em 1 o índice máximo.

As operações terminarão quando o índice máximo for zero, ou seja, quando coincidir com o primeiro índice (índice zero). Isto acontece pois um array de um elemento está de certeza ordenado.

QuickSort

O algoritmo QuickSort (desenvolvido em 1960 pelo cientista Charles Antony Richard Hoare) é de longe o algoritmo de ordenação mais usado e considerado pelo maior parte dos programadores como o melhor algoritmo dentro do género.

Este algoritmo implementa uma solução para a ordenação de um array baseado no famoso lema da informática “dividir para conquistar”. O que basicamente o QuickSort faz é ir dividindo o array, através da selecção de um pivot (elemento de referência), e ordenando depois cada parte.

Apresenta-se a seguir um exemplo de implementação do QuickSort:

void qsort (int v[], int inicio_v, int fim_v)
{
  //afectar os indices que irão percorrer o array com as posições iniciais e finais do array
  int a = inicio_v, b = fim_v;
 
  if (a >= b)
    return;
 
  //pivot (elemento do meio do array)
  int pivot = v[(a+b)/2];
 
  do {
    //ir pesquisando por números que estejam à esquerda do pivot e que sejam maiores que este
    while ( v[a] < pivot)
      ++a;    //incrementar "a" para se ir avançando no array
 
    //ir pesquisando por números que estejam à direita do pivot e que sejam menores que este
    while ( v[b] > pivot)
      --b;   //decrementar "b" para se ir regredindo no array 
 
    if (a <= b)  //trocar apenas se “a” menor ou igual a “b” 
    {
      if (v[a] != v[b])   //efectuar trocas apenas se os valores forem diferentes
        swap (v[a], v[b]);
      //incrementar "a" e decrementar "b" para se retomar as pesquisas
      ++a; --b;      
    }
  } while (a <= b);
 
  //quer-se ordenar um sub-array que vai desde o principio do array principal ate antes do pivot.
  //quando se terminam as pesquisas, "b" representa a posição antes do pivot.
  qsort (v, inicio_v, b);   
 
  //quer-se ordenar um sub-array que vai desde a posição seguinte ao pivot até ao fim do array
  //principal quando se terminam as pesquisas, "a" representa a posição seguinte ao pivot.
  qsort (v, a, fim_v);
}
 
void swap (int& a, int& b)
{
  //troca do conteudo das variáveis
  int aux = a; a = b; b = aux;
}

No fundo, este algoritmo pode-se resumir a sucessivas colocações de valores maiores que o pivot à sua direita e de valores menores à sua esquerda. No exemplo apresentado, o elemento escolhido como pivot é o elemento central de cada parte do array. Esta escolha tem tanto valor como qualquer outra. No entanto, se o array estiver parcialmente ordenado, ela é preferível.

Imagine-se o seguinte array (denomine-se o array por v): [1,3,1,2,5,4,3]. Vamos recorrer ao QuickSort para o ordenar:

  • Seleccionar o pivot. Para este caso o pivot será o elemento contido no índice 3 (elemento central), que contém o valor 2;
  • Colocar à esquerda do pivot só elementos menores que este e à direita só elementos maiores. Começando no princípio do array (pesquisar por elementos maiores ou iguais que o pivot), o elemento de índice 1 (valor 3) é maior que o pivot. Portanto, o elemento do índice 1 terá de ser trocado.

Nota: no exemplo apresentado, elementos iguais ao pivot tanto se podem encontrar à esquerda como à direita deste. No entanto, se durante a pesquisa de valores maiores ou menores que o pivot for encontrado algum elemento igual ao pivot, este será tomado para troca.

  • A pesquisa por elementos maiores que o pivot (e que estivessem inicialmente à esquerda deste) termina, tomando-se o valor v[1] para troca;
  • Para a pesquisa de valores menores que pivot e que estejam à sua direita (inicialmente), começa-se no índice final do array, com sucessivos decrementos. Como se pode observar, começando em v[6], o elemento v[3], que é o valor 2, é igual ao pivot (realce-se que o pivot é um valor). Ora, o ciclo while em que é feita a pesquisa por valores menores que o pivot, terminará para um valor igual ao pivot. Assim, será tomado para troca o valor contido em v[3].
  • Procede-se à troca. O valor que se usou para ir percorrendo o array ascendentemente (no exemplo é a variável a) é menor que o que se usou para percorrer o array de forma descendente (no exemplo é a variável b). Portanto, a condição a <= b é verdadeira, entrando-se assim no processo de troca de elementos;
  • Os elementos não são iguais (v[1] != v[3] é verdadeiro), logo todas as condições previstas para a troca estão satisfeitas;
  • Invoca-se a função de troca (swap()), que se encarregará de trocar os elementos;
  • Depois de trocados os elementos, fica-se com o vector v da seguinte forma: v = [1,2,1,3,5,4,3];
  • Os índices a e b são, respectivamente, incrementado e decrementado. Retoma-se, portanto, a pesquisa por valores maiores que o pivot em v[2] e a pesquisa por valores menores em v[2];
  • Durante a pesquisa por valores maiores, conclui-se que o elemento v[3] (contém o valor 3) é maior que pivot. Logo, será tomado para troca;
  • Já para as pesquisas por elementos menores que pivot, o elemento v[2] é igual que pivot, logo será tomado para troca;
  • No entanto, a troca não será efectuada, já que o índice usado para percorrer o array ascendentemente é maior que o usado para percorrer o array descendentemente. Desta forma, não se processa a troca de elementos (a é maior que b, logo a condição a <= b é falsa);
  • O ciclo do…while é também terminado, já que a condição de teste deste ciclo é a <= b;
  • Procede-se então às duas chamadas recursivas à função qsort(), sendo que na primeira chamada será apenas tomado em conta o sub-array [1,2,1] e na segunda o sub-array [3,5,4,3] (no entanto, para questões de indexação, o array em causa continua a ser o próprio v, sendo que para o segundo sub-array, v[3] representa o primeiro valor 3);
  • Para a primeira parte do array, o pivot será o valor 2 (v[1]), sendo que se troca v[1] (valor 2) e v[2] (valor 1);
  • Para a segunda parte do array, o pivot será o valor 5 (v[4]), sendo que a única troca que se efectua é entre v[4] (valor 5) e v[6] (valor 3);
  • Depois destas duas trocas, o array está totalmente ordenado;

O algoritmo QuickSort termina quando numa chamada recursiva a qsort(), o parâmetro inicio_v for maior ou igual a fim_v. Foi imposta esta condição terminal pois um array de um elemento está de certeza ordenado (se o índice que representa o início do array for o mesmo que representa o fim do array, então está-se na presença de um array de 1 elemento).

Algoritmos Clássicos – Pesquisa em Arrays

Tanto no mundo da programação, como no dia-a-dia, somos confrontados com diversas situações que requerem a pesquisa de algo num determinado conjunto de elementos, que em princípio terão características semelhantes ou iguais àquilo que se quer encontrar. Um exemplo muito simples, mas ilustrativo deste facto, é a situação em que se tem de encontrar um livro de uma disciplina dentro de uma mochila, na qual existem também outros materiais escolares (estojos, cadernos, etc.).

Em informática, o conceito e toda a logística em torno do pesquisar tem assumido um papel preponderante nos últimos anos. Exemplo disso é toda a agitação em torno dos diferentes motores de busca na Internet (Google, Yahoo!, etc.).

A própria programação não foge a esta regra. As pesquisas representam também uma operação com importância chave numa aplicação.

Uma maneira de encontrar algo no dia-a-dia poderá ser uma pesquisa sequencial aos elementos de um determinado conjunto. Ou seja, verificam-se, um a um, os elementos do conjunto até se encontrar o elemento pretendido. Este processo, apesar de se poder implementar em programação, não é de todo o melhor para se encontrar um elemento dentro de um conjunto de dados (por exemplo um array).

Neste contexto surge a pesquisa dicotómica, um algoritmo que facilita a procura de um certo elemento dentro de um array.

Pesquisa Dicotómica em Arrays

A pesquisa dicotómica em arrays (também muitas vezes referida como pesquisa binária) requer, antes de mais, que o array esteja ordenado. Ou seja, este algoritmo requer que antes da sua execução seja posto em execução um algoritmo de ordenação, tal como o QuickSort ou o BubbleSort.

Este algoritmo é provavelmente um dos mais simples e rápidos de entender dentro do mundo da programação. Este algoritmo propõe que se vá verificando sucessivamente o elemento central do array (que vai sendo divido em sub-arrays), fazendo uma comparação entre este e o elemento que se quer encontrar. Se o elemento central for menor que o valor que se deseja encontrar, então deverão analisar-se os elementos que estão à direita do elemento central. Caso o elemento central seja maior, deverá proceder-se à pesquisa na parte esquerda do array.

Se o elemento nunca for encontrado, então a função retorna -1, indicando que no array em questão não existe o elemento que se procurava.

Exemplo de implementação de pesquisa dicotómica em arrays:

int search (int v[], int find, int inicio_v, int fim_v)
{
  //se o delimitador à esquerda for maior que o da direita
  if (inicio_v > fim_v)
  //o elemento não existe no array em causa
    return -1;
 
  //elemento central (índice central do array)
  int pivot = (inicio_v+fim_v)/2;
 
  if (v[pivot] == find)        //se o elemento central for igual ao pretendido
    return pivot;             //indicar o índice em que se encontrou
 
  //se o valor central for maior que o valor a pesquisar
  if (v[pivot] > find)
    return search (v, find, inicio_v, pivot-1);  //pesquisar na parte esquerda do array
  //se o valor central for menor
  else
    return search (v, find, pivot+1, fim_v);    //pesquisar na parte direita do array
}

A função que implementa o algoritmo de pesquisa dicotómica em arrays (no exemplo é a função search), recebe como parâmetros o array a analisar (variável v), o valor a encontrar (variável find), o índice inicial da parte do array a ser analisada (variável inicio_v) e o índice final da parte do array a analisar (variável fim_v).

Esta função termina quando a condição inicio_v > fim_v for verdadeira. Pense-se no seguinte: após várias chamadas à função search() ocorre nova chamada à função, desta vez com uma parte do array principal que só apresenta um elemento. Neste caso, o pivot que será escolhido será esse mesmo elemento. Se o pivot não for igual ao valor que se procura, então de certeza que o valor que se procurava não existe no array. No entanto, o algoritmo continua a ser executado. Só que para ambas as possibilidades que se apresentam (o pivot ser maior que o valor que se procura ou ser menor), o parâmetro inicio_v será maior que fim_v.

Se o pivot for maior que o valor que se procura, então o parâmetro formal inicio_v terá o mesmo valor com que iniciou essa chamada à função, sendo que o parâmetro formal fim_v terá o valor de pivot – 1 (como se trata de uma parte do array que tem apenas um elemento, tanto inicio_v como fim_v têm o mesmo valor que pivot, logo fim_v será passado na nova chamada à função com um valor menor que inicio_v).

O outro caso que pode ocorrer (pivot ter um valor menor que o valor que se procura), o parâmetro formal inicio_v será afectado com o valor de pivot + 1 e o parâmetro formal fim_v terá o mesmo valor com que iniciou essa chamada à função (tal como no caso do pivot ser maior que o valor em procura, também neste caso fim_v e inicio_v têm o mesmo valor que é o valor de pivot).

Portanto, faz todo o sentido que quando fim_v for passado com um valor menor que inicio_v o algoritmo cesse, indicando-se que o valor que se procura não estava contido no array (return -1 indica a inexistência do valor dentro do array).

Algoritmos Clássicos – Gestão de Dados

Nos dias que correm, a gestão de dados através de aplicações informáticas é um domínio extremamente importante e em que se tem apostado fortemente em termos de desenvolvimento e pesquisa. Não é por isso de admirar que exista uma variedade tão grande de facilidades e algoritmos dentro deste ramo.

Desde sempre foi uma necessidade do ser humano ter a informação ordenada da melhor maneira possível, sendo que as técnicas usadas para a ordenação dessa informação foram evoluindo e transformando-se ao longo do tempo. E neste aspecto a informática não foi excepção. Desde que foi lançado o primeiro computador pessoal até à data actual, muita coisa se modificou na forma de gestão de dados. Os algoritmos responsáveis pela boa gestão de dados forem evoluindo, foram criadas plataformas específicas para gestão de dados (as tão famosas aplicações de gestão de base de dados, tais como Oracle, MySQL, SQL Server, Access, etc.). Como este é um ramo em constante transformação prevê-se que as inovações não cessem para já. Mais, é dito que as condições para mais evoluções e descobertas de soluções muitíssimo eficientes a este nível estão agora reunidas. Os algoritmos implementados em linguagens tradicionais (nomeadamente o OOP, Object-Oriented Programming) estão a começar a ser implementados em sistemas específicos de gestão de dados.

É um ramo da informática sobre o qual recaem imensas expectativas.