Nesta aula veremos três assuntos que aparecem em praticamente qualquer programa que manipula vetores (Aula 4): como procurar um valor em um vetor, como colocá-lo em ordem, e como gerar valores aleatórios (muito úteis em jogos, simulações e sorteios).

1. Complexidade de algoritmos

Existe mais de uma forma de resolver o mesmo problema, e algumas são bem mais "trabalhosas" que outras à medida que o vetor cresce. Para comparar algoritmos de forma simples, contamos, de forma aproximada, quantas operações (comparações, por exemplo) cada um faz em função do tamanho n do vetor:

Não precisamos de fórmulas exatas para isso — a ideia é só ter uma intuição de que "da ordem de n²" é bem mais custoso que "da ordem de n" para vetores grandes, mesmo que os dois resolvam corretamente o mesmo problema. Vamos usar essa intuição ao longo de toda a aula, para comparar os algoritmos que veremos.

2. Busca linear e busca binária

Busca linear

A busca linear (ou busca sequencial) é a forma mais simples de procurar um valor em um vetor: percorrer os elementos um a um, do início ao fim, comparando cada um com o valor procurado, até encontrá-lo ou até chegar ao final do vetor.

Como a busca pode parar assim que encontrar o valor (não precisamos continuar olhando o resto do vetor), usamos um while em vez de um for — o número de repetições não é fixo, depende de quando (e se) o valor for encontrado:

/* ---- Busca linear ---- */
#include <stdio.h>

int main() {
    int vetor[5] = {5, 12, 23, 8, 40};
    int procurado = 23;
    int posicao = -1;
    int i = 0;

    while (i < 5 && posicao == -1) {
        if (vetor[i] == procurado) {
            posicao = i; // encontrado: a condição "posicao == -1" já para o laço na próxima verificação
        }
        i++;
    }

    if (posicao != -1) {
        printf("Encontrado na posicao %d\n", posicao);
    } else {
        printf("Nao encontrado\n");
    }

    return 0;
}

"Animando" a busca por 23 no vetor [5, 12, 23, 8, 40], passo a passo (o ^ marca a posição sendo comparada):

[ 5, 12, 23,  8, 40]     [ 5, 12, 23,  8, 40]     [ 5, 12, 23,  8, 40]
  ^                             ^                        ^
5 != 23, continua       12 != 23, continua       23 == 23, encontrado! (posição 2, laço para aqui)

Intuição de complexidade

No melhor caso, o valor procurado é o primeiro do vetor: apenas 1 comparação. No pior caso — o valor está na última posição, ou nem está no vetor — é preciso comparar todos os n elementos. A busca linear é, portanto, da ordem de n no pior caso (Seção 1).

Busca binária

Se o vetor já estiver ordenado, existe uma forma muito mais rápida de buscar: a busca binária. A ideia é sempre comparar com o elemento do meio do intervalo de busca — se o valor procurado for menor, ele só pode estar na metade esquerda; se for maior, só pode estar na metade direita. A cada comparação, descartamos metade do que restava:

/* ---- Busca binária (o vetor precisa estar ordenado!) ---- */
#include <stdio.h>

int main() {
    int vetor[7] = {2, 5, 8, 12, 23, 40, 55};
    int procurado = 23;
    int baixo = 0, alto = 6, meio;
    int posicao = -1;

    while (baixo <= alto && posicao == -1) {
        meio = (baixo + alto) / 2;

        if (vetor[meio] == procurado) {
            posicao = meio; // encontrado no meio
        } else if (vetor[meio] < procurado) {
            baixo = meio + 1; // descarta a metade esquerda (incluindo o meio)
        } else {
            alto = meio - 1; // descarta a metade direita (incluindo o meio)
        }
    }

    if (posicao != -1) {
        printf("Encontrado na posicao %d\n", posicao);
    } else {
        printf("Nao encontrado\n");
    }

    return 0;
}

"Animando" a busca por 23 no vetor ordenado [2, 5, 8, 12, 23, 40, 55] (índices 0 a 6):

baixo=0, alto=6 -> meio=3 -> vetor[3]=12, 12 < 23 -> descarta [0..3], baixo=4
baixo=4, alto=6 -> meio=5 -> vetor[5]=40, 40 > 23 -> descarta [5..6], alto=4
baixo=4, alto=4 -> meio=4 -> vetor[4]=23, encontrado! (posição 4)

Em apenas 3 comparações, encontramos o valor em um vetor de 7 elementos — a busca linear, no pior caso, precisaria de até 7.

Intuição de complexidade

A cada comparação, a busca binária descarta metade do que restava — por isso, dobrar o tamanho do vetor soma apenas uma comparação a mais no pior caso, em vez de dobrar o número de comparações. Dizemos que ela é da ordem de log n (logaritmo de n): muito mais rápida que a busca linear para vetores grandes.

Ou seja: a busca binária é muito mais rápida, mas só pode ser usada quando o vetor já está ordenado — se não estiver, seria preciso ordená-lo primeiro (assunto da próxima seção), o que também tem um custo.

3. Introdução aos algoritmos de ordenação

Ordenar um vetor significa rearranjar seus elementos para que fiquem em ordem (crescente, por exemplo). Existem dezenas de algoritmos de ordenação; veremos aqui os dois mais didáticos para começar: Selection Sort e Bubble Sort.

3.1. Selection Sort (ordenação por seleção)

A ideia do Selection Sort: a cada passo, encontrar o menor elemento entre os que ainda não estão ordenados, e trocá-lo para a próxima posição correta.

/* ---- Selection Sort ---- */
#include <stdio.h>

int main() {
    int vetor[5] = {5, 2, 9, 1, 6};
    int n = 5;
    int i, j, posMenor, temp;

    for (i = 0; i < n - 1; i++) {
        posMenor = i; // assume que o menor da região ainda não ordenada é o primeiro dela

        for (j = i + 1; j < n; j++) {
            if (vetor[j] < vetor[posMenor]) {
                posMenor = j; // encontrou um menor ainda
            }
        }

        // troca o menor encontrado para a posição i
        temp = vetor[i];
        vetor[i] = vetor[posMenor];
        vetor[posMenor] = temp;
    }

    for (i = 0; i < n; i++) {
        printf("%d ", vetor[i]);
    }
    printf("\n");

    return 0;
}

"Animando" o Selection Sort sobre [5, 2, 9, 1, 6] (colchetes marcam a parte já ordenada):

[5, 2, 9, 1, 6]   -> menor da região toda é 1 (posição 3)   -> troca com a posição 0
[1| 2, 9, 5, 6]   -> menor do restante (2,9,5,6) é 2 (já na posição 1)   -> nada a trocar
[1, 2| 9, 5, 6]   -> menor do restante (9,5,6) é 5 (posição 3)   -> troca com a posição 2
[1, 2, 5| 9, 6]   -> menor do restante (9,6) é 6 (posição 4)   -> troca com a posição 3
[1, 2, 5, 6| 9]   -> sobrou só um elemento: pronto!
[1, 2, 5, 6, 9]   -> vetor ordenado

A barra | mostra a fronteira entre a parte já ordenada (à esquerda) e a parte ainda não ordenada (à direita) — essa fronteira avança uma posição a cada volta do laço externo.

Intuição de complexidade

Para colocar o menor elemento na posição 0, o Selection Sort precisa examinar todos os n elementos. Para a posição 1, examina os n - 1 restantes. E assim por diante: n + (n-1) + (n-2) + ... + 1, que é da ordem de n² comparações — bem mais custoso que a busca linear, especialmente para vetores grandes: dobrar o tamanho do vetor pode quadruplicar o número de comparações.

3.2. Bubble Sort (ordenação por bolha)

A ideia do Bubble Sort: percorrer o vetor repetidamente, comparando pares de elementos vizinhos e trocando-os de lugar sempre que estiverem fora de ordem. A cada passagem completa, o maior elemento "sobe" (como uma bolha) até sua posição final, no final do vetor.

/* ---- Bubble Sort ---- */
#include <stdio.h>

int main() {
    int vetor[4] = {5, 2, 9, 1};
    int n = 4;
    int i, j, temp;

    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - 1 - i; j++) {
            if (vetor[j] > vetor[j + 1]) { // vizinhos fora de ordem
                temp = vetor[j];
                vetor[j] = vetor[j + 1];
                vetor[j + 1] = temp;
            }
        }
    }

    for (i = 0; i < n; i++) {
        printf("%d ", vetor[i]);
    }
    printf("\n");

    return 0;
}

"Animando" a primeira passagem do Bubble Sort sobre [5, 2, 9, 1], comparando sempre um par de vizinhos:

[5, 2, 9, 1]   compara (5,2): fora de ordem -> troca
[2, 5, 9, 1]   compara (5,9): em ordem -> mantém
[2, 5, 9, 1]   compara (9,1): fora de ordem -> troca
[2, 5, 1, 9]   fim da 1a passagem: o maior (9) já "borbulhou" até o final

Nas passagens seguintes, o mesmo processo se repete sobre a parte ainda não ordenada (sem mexer mais no 9, que já está no lugar certo), até o vetor inteiro ficar ordenado: [1, 2, 5, 9].

Intuição de complexidade

Assim como no Selection Sort, o Bubble Sort compara pares de elementos repetidamente até não haver mais trocas necessárias — no pior caso (vetor em ordem decrescente, por exemplo), o número de comparações também é da ordem de n². Na prática, os dois algoritmos são úteis para aprender os conceitos de ordenação, mas raramente usados em programas "de verdade" com vetores grandes — algoritmos mais eficientes serão vistos mais adiante, caso vocês continuem para a disciplina de Estruturas de Dados.

4. Números pseudoaleatórios

Muitos programas (jogos, simulações, sorteios) precisam de números "aleatórios". Na prática, um computador não gera números verdadeiramente aleatórios — ele usa uma fórmula matemática que produz uma sequência de números que parecem aleatórios, por isso chamados de pseudoaleatórios. Em C, isso é feito com duas funções de <stdlib.h>, mais uma de <time.h>:

Se não chamarmos srand(), ou sempre usarmos a mesma semente fixa, rand() vai gerar exatamente a mesma sequência de números toda vez que o programa rodar — o que é ótimo para testes, mas ruim para um jogo "de verdade". Por isso, é comum inicializar a semente com o horário atual, que muda a cada execução:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main() {
    srand(time(NULL)); // inicializa a semente uma única vez, no início do programa

    printf("%d\n", rand()); // um número qualquer entre 0 e RAND_MAX

    return 0;
}

Gerando números em uma faixa específica

rand() sozinho gera números em uma faixa enorme (0 a RAND_MAX), raramente útil diretamente. Para obter um número em uma faixa menor, usamos o operador % (Aula 1):

int numero = rand() % n; // gera um número entre 0 e (n - 1)

Para deslocar essa faixa para começar em outro valor (não em 0), somamos o valor inicial desejado:

int numero = minimo + rand() % (maximo - minimo + 1); // entre minimo e maximo, incluindo os dois

Por exemplo, simulando o lançamento de um dado de 20 lados (um "d20", comum em jogos de RPG), que deve sortear um valor entre 1 e 20:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main() {
    int d20;

    srand(time(NULL));

    d20 = 1 + rand() % 20; // 1 + (0 a 19) = 1 a 20

    printf("Voce tirou %d no d20!\n", d20);

    return 0;
}

Aqui, rand() % 20 produz um valor entre 0 e 19 (20 possibilidades); somando 1, obtemos um valor entre 1 e 20 — exatamente as faces de um dado de 20 lados.

Resumo

Exercícios

Nível fácil

1. Escreva um programa que leia um vetor de 10 inteiros e um valor a procurar, e implemente a busca linear diretamente na main() (sem usar funções) para informar se o valor foi encontrado e em qual posição.
2. Escreva um programa que simule o lançamento de um dado comum (6 lados), sorteando e imprimindo um valor entre 1 e 6.
3. Escreva um programa que leia um vetor de 5 inteiros e o ordene implementando o Selection Sort diretamente na main(), imprimindo o vetor antes e depois de ordenado.

Nível médio

4. Escreva um programa que gere um vetor de 10 números aleatórios entre 1 e 100 (usando rand(), sem pedir os valores ao usuário) e o ordene implementando o Bubble Sort diretamente na main(), imprimindo o vetor antes e depois de ordenado.
5. Modifique a busca linear do Exercício 1 para trabalhar sobre um vetor já ordenado, parando de procurar imediatamente assim que encontrar um elemento maior que o procurado — já que, em um vetor ordenado, isso significa que o valor procurado não existe. Compare quantas comparações essa versão faz, no pior caso, em relação à busca linear comum.
6. Escreva um programa que simule o lançamento de dois dados de 6 lados (2d6, como em jogos de tabuleiro) e conte, em 10.000 lançamentos simulados, quantas vezes a soma dos dois dados deu exatamente 7.

Nível difícil

7. Modifique o Bubble Sort do Exercício 4 para que ele pare mais cedo caso o vetor já esteja ordenado antes de completar todas as n-1 passagens (dica: use uma flag que informa se alguma troca ocorreu durante a passagem — se nenhuma troca ocorreu, o vetor já está ordenado, e o laço pode parar).
8. Escreva um programa que gere um vetor com 20 números aleatórios entre 1 e 100, sem repetição (nenhum número deve aparecer duas vezes no vetor). Dica: ao sortear um novo número, utilize a busca linear para verificar se ele já está no vetor antes de aceitá-lo.

Sugestões de Respostas dos Exercícios

#include <stdio.h>

int main() {
    int vetor[10];
    int i, procurado, posicao = -1;

    for (i = 0; i < 10; i++) {
        printf("Digite o valor %d: ", i + 1);
        scanf("%d", &vetor[i]);
    }

    printf("Qual valor procurar? ");
    scanf("%d", &procurado);

    i = 0;
    while (i < 10 && posicao == -1) {
        if (vetor[i] == procurado) {
            posicao = i;
        }
        i++;
    }

    if (posicao != -1) {
        printf("Encontrado na posicao %d\n", posicao);
    } else {
        printf("Nao encontrado\n");
    }

    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main() {
    int dado;

    srand(time(NULL));
    dado = 1 + rand() % 6;

    printf("Voce tirou %d\n", dado);

    return 0;
}

#include <stdio.h>

int main() {
    int vetor[5];
    int n = 5;
    int i, j, posMenor, temp;

    for (i = 0; i < n; i++) {
        printf("Digite o valor %d: ", i + 1);
        scanf("%d", &vetor[i]);
    }

    printf("Antes: ");
    for (i = 0; i < n; i++) printf("%d ", vetor[i]);
    printf("\n");

    for (i = 0; i < n - 1; i++) {
        posMenor = i;
        for (j = i + 1; j < n; j++) {
            if (vetor[j] < vetor[posMenor]) {
                posMenor = j;
            }
        }
        temp = vetor[i];
        vetor[i] = vetor[posMenor];
        vetor[posMenor] = temp;
    }

    printf("Depois: ");
    for (i = 0; i < n; i++) printf("%d ", vetor[i]);
    printf("\n");

    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main() {
    int vetor[10];
    int n = 10;
    int i, j, temp;

    srand(time(NULL));

    for (i = 0; i < n; i++) {
        vetor[i] = 1 + rand() % 100;
    }

    printf("Antes: ");
    for (i = 0; i < n; i++) printf("%d ", vetor[i]);
    printf("\n");

    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - 1 - i; j++) {
            if (vetor[j] > vetor[j + 1]) {
                temp = vetor[j];
                vetor[j] = vetor[j + 1];
                vetor[j + 1] = temp;
            }
        }
    }

    printf("Depois: ");
    for (i = 0; i < n; i++) printf("%d ", vetor[i]);
    printf("\n");

    return 0;
}

int i;
int posicao = -1;

for (i = 0; i < n; i++) {
    if (vetor[i] == procurado) {
        posicao = i;
        break;
    }
    if (vetor[i] > procurado) {
        // já passou do ponto onde o valor poderia estar: para de procurar
        break;
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main() {
    int i, dado1, dado2;
    int contadorSete = 0;

    srand(time(NULL));

    for (i = 0; i < 10000; i++) {
        dado1 = 1 + rand() % 6;
        dado2 = 1 + rand() % 6;

        if (dado1 + dado2 == 7) {
            contadorSete++;
        }
    }

    printf("Somas iguais a 7: %d de 10000\n", contadorSete);

    return 0;
}

int i, j, temp;
int houveTroca;

for (i = 0; i < n - 1; i++) {
    houveTroca = 0; // flag: nenhuma troca ainda nesta passagem

    for (j = 0; j < n - 1 - i; j++) {
        if (vetor[j] > vetor[j + 1]) {
            temp = vetor[j];
            vetor[j] = vetor[j + 1];
            vetor[j + 1] = temp;
            houveTroca = 1; // aconteceu uma troca
        }
    }

    if (!houveTroca) { // nenhuma troca: já está ordenado
        break;
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main() {
    int vetor[20];
    int quantidade = 0;
    int candidato;
    int i;
    int jaExiste;

    srand(time(NULL));

    while (quantidade < 20) {
        candidato = 1 + rand() % 100;

        // busca linear sobre a parte ja preenchida, para ver se o candidato ja existe
        jaExiste = 0;
        for (i = 0; i < quantidade; i++) {
            if (vetor[i] == candidato) {
                jaExiste = 1;
            }
        }

        // só aceita o candidato se ele ainda não estiver no vetor
        if (!jaExiste) {
            vetor[quantidade] = candidato;
            quantidade++;
        }
    }

    printf("Numeros sorteados: ");
    for (i = 0; i < 20; i++) {
        printf("%d ", vetor[i]);
    }
    printf("\n");

    return 0;
}