Este repositório contém implementações de dois algoritmos fundamentais em ciência da computação: Bubble Sort e busca binária, em linguagem C. Abaixo, uma breve descrição de cada algoritmo e como eles funcionam.
O Bubble Sort é um algoritmo de ordenação simples que compara repetidamente pares de elementos adjacentes em um vetor e os troca se estiverem fora de ordem. O processo é repetido até que nenhum par de elementos precise ser trocado.
// Definindo o Bubble Sort
void bubbleSort (int lista[], int tamanho){
for (int i = 0; i < tamanho; i++){ // Loop externo para passar por todos os elementos
for (int j = 0; j < tamanho - i - 1; j++){ // Loop interno para passar por todos os elementos menos o último
if(lista[j] > lista[j + 1]) { // Comparando elementos adjacentes e trocando se estiverem na ordem errada
int temp = lista[j]; // Troca o elemento com o posterior
lista[j] = lista[j + 1]; // Troca o elemento com o posterior
lista[j + 1] = temp; // Troca o elemento com o posterior
}
}
}
}-
Começa com o primeiro elemento do vetor e compara-o com o próximo elemento.
-
Se o primeiro elemento for maior que o próximo elemento, os dois elementos são trocados.
-
Esse processo de comparação e troca é repetido para cada par de elementos adjacentes no vetor, avançando de um extremo ao outro.
-
Após a primeira passagem completa pelo vetor, o maior elemento estará na última posição.
-
Em seguida, o processo é repetido para o sub-vetor restante (todos os elementos, exceto o último) para colocar o segundo maior elemento em sua posição correta.
-
O processo continua até que nenhum par de elementos precise ser trocado em uma passagem completa pelo vetor.
-
O vetor está agora ordenado, com os elementos em ordem crescente (ou decrescente, dependendo da implementação).
A busca binária é um algoritmo de busca eficiente que opera em vetores ordenados. Ela divide o vetor pela metade e compara o elemento do meio com o valor desejado, ajustando o intervalo de busca de acordo com o resultado da comparação. O processo é repetido até encontrar o elemento ou determinar que ele está ausente.
// Definindo a busca binária
int buscaBinaria(int lista[], int tamanho, int numero) {
int inicio = 0; // Índice inicial
int fim = tamanho - 1; // Índice final
// Loop enquanto a busca não estiver completa
while (inicio <= fim) { // Continua enquanto o início for menor ou igual ao fim.
int meio = (fim + inicio) / 2; // Calcula o índice do meio
// Retorna o índice se o elemento for encontrado
if (lista[meio] == numero)
return meio;
if (lista[meio] < numero)
inicio = meio + 1; // Busca na parte direita do vetor
else
fim = meio - 1; // Busca na parte esquerda do vetor
}
return -1; // O elemento não for encontrado
}-
Inicialização: Começa com dois índices, inicio e fim, que representam o intervalo de busca. inicio é definido como o índice do primeiro elemento do vetor, e fim como o índice do último elemento.
-
Loop de Busca: Dentro de um loop, calcula o índice do elemento do meio, chamado de meio, que é a média entre inicio e fim.
-
Comparação: Compara o elemento no índice meio com o valor desejado (numero).
-
Casos de Comparação: Existem três casos possíveis:
- Se o elemento no índice meio for igual ao numero, o elemento foi encontrado, e o índice meio é retornado.
- Se o elemento no índice meio for menor que numero, atualiza inicio para meio + 1, continuando a busca na parte direita do vetor.
- Se o elemento no índice meio for maior que numero, atualiza fim para meio - 1, continuando a busca na parte esquerda do vetor.
- Continuação da Busca: O loop continua até que inicio seja maior do que fim. Nesse ponto, se o elemento ainda não foi encontrado, é determinado que ele não está presente no vetor.
- Resultado: Se o elemento é encontrado, a função retorna o índice onde o elemento foi encontrado. Caso contrário, retorna -1 para indicar que o elemento não está no vetor.