Hoje, vou falar sobre um algoritmo de ordenação bastante simples, o bubble sort (algo como ordenação “por bolha” em português). Esse algoritmo não costuma ser utilizado em aplicações reais por não ser um algoritmo muito eficiente. Na verdade, ele costuma ser ensinado nas aulas de algoritmos e estruturas de dados devido à sua simplicidade, servindo de base de comparação para algoritmos mais complexos.
Uma vantagem do bubble sort é que a lógica do algoritmo tão simples que, uma vez que a gente pega o jeito, conseguimos implementar o algoritmo “de cabeça”. Isso pode ser bastante útil se precisarmos realizar uma tarefa de ordenação sem consultar materiais didáticos ou em pouco tempo, como é o caso em competições de programação e entrevistas de emprego na área de desenvolvimento de software.
O que são algoritmos de ordenação
Algoritmos de ordenação são aqueles algoritmos que recebem sequências desordenadas de elementos, como listas de nomes de pessoas, ou números embaralhados, e às transformam em sequências ordenadas (ou retornam uma nova sequência ordenada, a depender da implementação).
Vale notar que se você precisar de um algoritmo de ordenamento para uma aplicação real em C, a stdlib.h oferece uma função genérica de ordenamento denominada qsort(), que implementa um algoritmo de ordenamento muito mais eficiente chamado de quicksort. Entretanto, sua utilização é um pouquinho mais complicada.
Utilização do bubble sort para ordenar inteiros
O bubble sort recebe esse nome porque no processo de ordenação de números, se visualizarmos a lista de números como uma coluna, os números maiores são empurrados para a parte de baixo da sequência, enquanto os números menores caminham lentamente para o topo, lembrando o movimento de uma bolha embaixo d’água.
Vamos ver uma implementação do bubble sort em C que ordena inteiros de forma crescente, e explicá-la passo a passo em seguida.
#include <stdio.h> //printf, scanf
#include <stdbool.h> //bool, true, false
int main(void){
int tamanho; //tamanho do vetor
printf("Digite a quantidade de números na sequência:");
scanf("%d", &tamanho);
int sequencia[tamanho];
/*Coleta dos dados*/
printf("Digite os números da sequência:");
for (int i = 0; i < tamanho; i++)
scanf("%d", &sequencia[i]);
int temp;
bool mudanca = true;
while (mudanca){
mudanca = false;
for (int i = 0; i < tamanho-1; i++){
if (sequencia[i] > sequencia[i+1]){
/*Realiza a troca*/
temp = sequencia[i];
sequencia[i] = sequencia[i+1];
sequencia[i+1] = temp;
mudanca = true;
}
}
}
printf("Sequencia reordenada:\n");
for (int i = 0; i < tamanho; i++)
printf("%d ", sequencia[i]);
printf("\n");
}
(Obs: talvez você não esteja familiarizado/a com a biblioteca stdbool.h. Ela é pertence ao conjunto de bibliotecas padrão do C, assim como a stdio.h, e basicamente permite que utilizemos o tipo bool e as macros true e false, ao invés dos valores 1 e 0, respectivamente. Eu gosto de utilizá-la para melhorar a semântica do código.)
Funciona assim: um laço de repetição interno percorre a sequência a ser ordenada, do primeiro elemento até o penúltimo, comparando cada elemento com o elemento seguinte. Se o primeiro elemento for menor que o seguinte, tudo ok! Mas se o primeiro for maior que o segundo, então os dois elementos trocam de lugar.
Por exemplo, se tivermos a sequência 1, 2, 7, 5, o algoritmo compararia 1 e 2 e não faria nada, depois 2 e 7 e não faria nada, depois 7 e 5, e então ele trocaria esses dois elementos de lugar, tornando a sequência 1, 2, 5, 7.
Nesse caso, nossa sequência já estaria ordenada. Por outro lado, se a sequência fosse 1, 2, 7, 5, 4, se trocássemos o 7 e 5 de lugar, então ela viraria 1, 2, 5, 7, 4. Depois compararíamos o 7 com o 4, trocaríamos os dois de lugar, e teríamos 1, 2, 5, 4, 7. Como o laço interno já chegou ao penúltimo elemento, então ele para. Mas a sequência ainda não está ordenada. Para ordená-la, o laço precisa ser executado mais uma vez para trocar o 5 de lugar com o 4.
Por isso temos um laço mais externo (o laço while), responsável por fazer com o que o laço interno seja repetido quantas vezes forem necessárias para que a sequência seja toda ordenada. A forma como controlamos quando o laço externo deve parar é simples. Em nosso exemplo, fazemos isso através da variável mudanca.
Enquanto o laço interno (o laço for) fizer modificações na sequência, o algoritmo deve ser repetido. Até que ele percorra toda a sequência sem encontrar mais nenhum elemento para trocar de lugar. Então, quando o laço interno modificar a sequência, ele avisa, alterando o valor de mudanca para true. Como alteramos o valor de mudanca para false no início de cada iteração do laço while, a sequência estará ordenada quando o laço mais interno percorrer toda a sequência sem alterar mudanca para true de novo.
Exemplo de saída do programa:
Digite a quantidade de números na sequência:10 Digite os números da sequência:47 30 777 1 0 66 434 23 8 1 Sequencia reordenada: 0 1 1 8 23 30 47 66 434 777
Utilização do bubble sort para ordenar strings
É possível que ao invés de números, você precise ordenar palavras. Nesse caso, o C não permite que façamos comparações e atribuições de valores do mesmo modo como fazemos com inteiros. Não podemos escrever algo como if (string1 > string2), e se tentarmos utilizar uma atribuição como string1 = string2, apenas faremos com que string1 se refira à string contida na string2, então se alterarmos o valor string2, a string1 apontará para esse valor modificado.
Felizmente, a biblioteca padrão do C nos provê as ferramentas necessárias para fazer esse tipo de coisa. A biblioteca string.h possui duas funções úteis para nós: strcmp() e strcpy().
Comparando strings
A função strcmp() recebe como argumentos dois ponteiros para char (não esqueçamos que em C, strings são sequências de caracteres, identificadas pelo endereço do primeiro caractere), e retorna algum valor obedecendo as seguintes condições:
- um valor negativo, se a primeira string for menor que a segunda.
- 0 (zero) se as duas strings forem iguais.
- um valor positivo, se a primeira string for maior que a segunda.
Então, podemos substituir a parte do nosso código que verifica se um elemento da sequência é maior que o outro da seguinte maneira:
if (strcmp(sequencia[i], sequencia[i+1]) > 0)
Trocando a posição das strings
Para trocar a posição das strings, utilizamos a função strcpy(), que recebe duas strings como argumento e coloca o valor da segunda na primeira. Então, fazemos a troca da posição das strings na sequência alterando o código:
temp = sequencia[i];
sequencia[i] = sequencia[i+1];
sequencia[i+1] = temp;
Para:
strcpy(temp, sequencia[i]);
strcpy(sequencia[i], sequencia[i+1]);
strcpy(sequencia[i+1], temp);
Abaixo, temos um exemplo completo de algoritmo de bubble sort para strings em C:
#include <stdio.h> //printf, scanf
#include <string.h> //strcmp, strcpy
#include <stdbool.h> //bool, true, false
#define TAM_MAX 20 //O tamanho maximo de cada string
int main(void){
int tamanho; //tamanho do vetor
printf("Digite a quantidade de nomes:");
scanf("%d", &tamanho);
char sequencia[tamanho][TAM_MAX];
/*Coleta dos dados*/
printf("Digite os nomes da sequência:");
for (int i = 0; i < tamanho; i++)
scanf("%s", &sequencia[i]);
char temp[TAM_MAX];
bool mudanca = true;
while (mudanca){
mudanca = false;
for (int i = 0; i < tamanho-1; i++){
if (strcmp(sequencia[i], sequencia[i+1]) > 0){
/*Realiza a troca*/
strcpy(temp, sequencia[i]);
strcpy(sequencia[i], sequencia[i+1]);
strcpy(sequencia[i+1], temp);
mudanca = true;
}
}
}
printf("Sequencia reordenada:\n");
for (int i = 0; i < tamanho; i++)
printf("%s ", sequencia[i]);
printf("\n");
}
Observe que como strings são vetores de caracteres, precisamos criar um array bidimensional para dar conta de uma lista de nomes, entretanto, quando passamos o nosso vetor como argumento para o scanf ou printf, não precisamos escrever sequencia[i][0], pois sequencia[i] já contém o endereço do primeiro caractere do elemento da lista em questão.
Espero que tenha gostado do post, e continue acompanhando o blog para ficar por dentro de mais conteúdo sobre algoritmos e estruturas de dados em C!
