Prática: Vetores e Funções

Por mais técnicas que você aprenda, são apenas teoria até entrar no ringue. Este capítulo integra vetores, funções e ponteiros através de quatro projetos práticos para testar suas habilidades reais.

Projeto 1: Bubble Sort

Bubble sort é o algoritmo de ordenação mais básico. A ideia é percorrer repetidamente o vetor, comparando elementos adjacentes e trocando-os se estiverem na ordem errada, até que nenhuma troca ocorra. Cada passagem "borbulha" o maior valor atual para o final.

Passos do algoritmo

1. Comece pelo primeiro elemento e compare cada par de elementos adjacentes
2. Se o elemento à esquerda é maior que o da direita, troque-os
3. Após uma passagem, o maior valor está na posição correta
4. Repita para a porção restante até estar totalmente ordenado

Implementação

`c #include <stdio.h>

void bubble_sort(int *arr, int len) { int i, j; int swapped;

for (i = 0; i < len - 1; i++) {
    swapped = 0;
    for (j = 0; j < len - 1 - i; j++) {
        if (arr[j] > arr[j + 1]) {
            int temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
            swapped = 1;
        }
    }
    if (!swapped) break;
}

}

void print_array(const int *arr, int len) { int i; for (i = 0; i < len; i++) { printf("%d ", arr[i]); } printf("\n"); }

int main(void) { int data[] = {64, 34, 25, 12, 22, 11, 90}; int len = sizeof(data) / sizeof(data[0]);

printf("Before: ");
print_array(data, len);

bubble_sort(data, len);

printf("After:  ");
print_array(data, len);

return 0;

} `

ext Before: 64 34 25 12 22 11 90 After: 11 12 22 25 34 64 90

A otimização com flag swapped: se nenhuma troca ocorrer durante uma passagem, o vetor já está ordenado e o algoritmo termina antecipadamente. No melhor caso (já ordenado), a complexidade de tempo cai para O(n).

Exemplo

Ordene notas em ordem decrescente usando bubble sort:

`c #include <stdio.h>

void sort_desc(int *arr, int len) { int i, j, swapped; for (i = 0; i < len - 1; i++) { swapped = 0; for (j = 0; j < len - 1 - i; j++) { if (arr[j] < arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; swapped = 1; } } if (!swapped) break; } }

int main(void) { int scores[] = {85, 92, 78, 95, 88}; int len = sizeof(scores) / sizeof(scores[0]); int i;

sort_desc(scores, len);
printf("Ranking: ");
for (i = 0; i < len; i++) {
    printf("%d ", scores[i]);
}
printf("\n");
return 0;

} `

ext Ranking: 95 92 88 85 78

Para ordem decrescente, basta mudar a comparação de > para <.

Projeto 2: Busca Binária

Busca binária localiza eficientemente um valor alvo em um vetor ordenado dividindo o intervalo de busca pela metade a cada passo.

Passos do algoritmo

1. Defina o intervalo de busca como [low, high]
2. Calcule a posição do meio: mid = (low + high) / 2
3. Se rr[mid] é igual ao alvo, foi encontrado
4. Se rr[mid] é menor que o alvo, busque na metade direita
5. Se rr[mid] é maior que o alvo, busque na metade esquerda
6. Se o intervalo se reduz a vazio sem encontrar, o alvo não existe

Implementação

`c #include <stdio.h>

int binary_search(const int *arr, int len, int target) { int low = 0; int high = len - 1;

while (low <= high) {
    int mid = low + (high - low) / 2;

    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        low = mid + 1;
    } else {
        high = mid - 1;
    }
}

return -1;

}

int main(void) { int data[] = {2, 5, 8, 12, 16, 23, 38, 45, 56, 78}; int len = sizeof(data) / sizeof(data[0]); int targets[] = {23, 7, 78, 1}; int num = sizeof(targets) / sizeof(targets[0]); int i;

for (i = 0; i < num; i++) {
    int pos = binary_search(data, len, targets[i]);
    if (pos >= 0) {
        printf("%d found at index %d\n", targets[i], pos);
    } else {
        printf("%d not found\n", targets[i]);
    }
}
return 0;

} `

ext 23 found at index 5 7 not found 78 found at index 9 1 not found

A complexidade de tempo é O(log n); 1 bilhão de elementos exige no máximo 30 comparações.

Exemplo

Encontre a posição do primeiro elemento maior ou igual ao alvo (busca de limite inferior):

`c #include <stdio.h>

int lower_bound(const int *arr, int len, int target) { int low = 0; int high = len; while (low < high) { int mid = low + (high - low) / 2; if (arr[mid] < target) { low = mid + 1; } else { high = mid; } } return low; }

int main(void) { int data[] = {1, 3, 3, 5, 7, 7, 7, 9, 11}; int len = sizeof(data) / sizeof(data[0]); int pos = lower_bound(data, len, 7); printf("First >= 7 at index %d, value=%d\n", pos, data[pos]); return 0; } `

ext First >= 7 at index 4, value=7

Busca de limite inferior é extremamente comum em programação competitiva e na STL.

Projeto 3: Inversão de Strings

Troque os caracteres da frente e de trás de uma string, ex.: "hello" torna-se "olleh". Use a técnica de dois ponteiros para operação in-place, sem vetor extra.

Implementação

`c #include <stdio.h> #include <string.h>

void str_reverse(char *s) { char *left = s; char *right = s + strlen(s) - 1;

while (left < right) {
    char temp = *left;
    *left = *right;
    *right = temp;
    left++;
    right--;
}

}

int main(void) { char s1[] = "Hello World"; char s2[] = "ABCDE"; char s3[] = "racecar";

str_reverse(s1);
str_reverse(s2);
str_reverse(s3);

printf("%s\n", s1);
printf("%s\n", s2);
printf("%s\n", s3);

return 0;

} `

ext dlroW olleH EDCBA racecar

Nota: você deve usar um vetor de caracteres (modificável), não um ponteiro para um literal de string.

Exemplo

Verifique se uma string é um palíndromo (ignorando caracteres não alfanuméricos, sem distinguir maiúsculas/minúsculas):

`c #include <stdio.h> #include <string.h> #include <ctype.h>

int is_palindrome(const char *s) { const char *left = s; const char *right = s + strlen(s) - 1; while (left < right) { while (left < right && !isalnum((unsigned char)*left)) left++; while (left < right && !isalnum((unsigned char)*right)) right--; if (tolower((unsigned char)*left) != tolower((unsigned char)*right)) { return 0; } left++; right--; } return 1; }

int main(void) { printf("%d\n", is_palindrome("racecar")); printf("%d\n", is_palindrome("hello")); printf("%d\n", is_palindrome("A man a plan a canal Panama")); return 0; } `

ext 1 0 1

Projeto 4: Análise de Frequência de Caracteres

Conte quantas vezes cada caractere aparece em uma string — uma operação fundamental de análise de texto.

Implementação

`c #include <stdio.h> #include <string.h>

void char_freq(const char *s, int *freq, int size) { int i; for (i = 0; i < size; i++) freq[i] = 0; while (*s != '\0') { unsigned char ch = (unsigned char)*s; if (ch < (unsigned)size) freq[ch]++; s++; } }

int main(void) { char text[] = "Hello World!"; int freq[256] = {0}; int i;

char_freq(text, freq, 256);

for (i = 32; i < 127; i++) {
    if (freq[i] > 0) printf("'%c': %d  ", i, freq[i]);
}
printf("\n");
return 0;

} `

ext ' ': 1 '!': 1 'H': 1 'W': 1 'd': 1 'e': 1 'l': 3 'o': 2 'r': 1

Usando valores ASCII como índices do vetor, uma única passagem completa a contagem. 256 posições cobrem todos os caracteres de 8 bits.

Exemplo

Conte frequências de letras e encontre a letra mais frequente:

`c #include <stdio.h> #include <ctype.h> #include <string.h>

void letter_freq(const char *s, int *freq) { int i; for (i = 0; i < 26; i++) freq[i] = 0; while (*s != '\0') { if (isalpha((unsigned char)*s)) { freq[tolower((unsigned char)*s) - 'a']++; } s++; } }

char find_max(const int *freq, int size) { int max_idx = 0; int i; for (i = 1; i < size; i++) { if (freq[i] > freq[max_idx]) max_idx = i; } return 'a' + max_idx; }

int main(void) { const char *text = "The quick brown fox jumps over the lazy dog"; int freq[26]; letter_freq(text, freq); char max_ch = find_max(freq, 26); printf("Most frequent letter: %c (%d times)\n", max_ch, freq[max_ch - 'a']); return 0; } `

ext Most frequent letter: o (4 times)

❓ Perguntas Frequentes

P: Qual é melhor, bubble sort ou selection sort? R: Ambos têm complexidade de tempo O(n^2), mas bubble sort tem uma otimização de término antecipado com O(n) no melhor caso. A diferença prática é pequena; nenhum dos dois é adequado para grandes conjuntos de dados.

P: Quais são os pré-requisitos para busca binária? R: O vetor deve estar ordenado e suportar acesso aleatório. Listas encadeadas não podem usar busca binária porque você não pode acessar o elemento do meio em O(1).

P: Existe uma função de biblioteca para inversão de strings? R: A biblioteca padrão C não tem uma função de inversão direta. C++ tem std::reverse em <algorithm>; em C, você deve implementá-la.

P: Por que usar um vetor de 256 elementos para contagem de frequência? R: unsigned char varia de 0 a 255, totalizando 256 valores. Usando o valor ASCII do caractere como índice, 256 posições cobrem todos os caracteres possíveis, e uma única passagem completa a contagem.

📖 Resumo

• Bubble sort ordena trocando elementos adjacentes; a flag swapped permite término antecipado
• Busca binária requer um vetor ordenado; eficiência O(log n) supera amplamente a busca linear
• A técnica de dois ponteiros inverte strings in-place com complexidade de espaço O(1)
• Análise de frequência de caracteres usa valores ASCII como índices de vetor, completando em uma passagem
• Estes projetos demonstram as três habilidades centrais: armazenamento em vetores, encapsulamento em funções e manipulação com ponteiros

📝 Exercícios

1. Aprimore bubble sort: implemente uma função que pode ordenar tanto em ordem crescente quanto decrescente, controlada por um parâmetro de ponteiro de função.
2. Implemente uma versão recursiva de busca binária: int bin_search_rec(const int *arr, int low, int high, int target).
3. Escreva um analisador de frequência de caracteres aprimorado: leia uma linha de entrada do usuário, depois exiba os 3 caracteres mais frequentes e suas contagens.