Módulo 0Kit de sobrevivência em C

Antes de ordenar ou buscar qualquer coisa, tem que conseguir ler um programa em C. Aqui vai só o mínimo, sem enrolação.

Programa = receita de bolo Visto em aula · 13/08

Toda instrução termina com ;. Bloco fica entre { }. O que vem depois de // ou entre /* */ é comentário -> o compilador ignora, é só pra gente.

Variável = caixa com etiqueta Visto em aula · 13/08

Contas que pegam iniciante Visto em aula · 13/08

• 7 / 2 dá 3, não 3.5. Inteiro dividido por inteiro -> corta a parte quebrada e pronto. Quer 3.5? -> (double) 7 / 2.
• 7 % 2 dá 1 -> é o resto da divisão. 137 % 10 = 7, ou seja, o último dígito. É isso que tá por trás do rand() % 100 da aula e da tabela hash.
• = guarda. == pergunta "é igual?". Trocar um pelo outro dentro do if é o erro nº 1 de C.
• && = E (as duas verdadeiras). || = OU (pelo menos uma). ! = NÃO.
• i++ soma 1. i-- tira 1. soma += x é só atalho de soma = soma + x.

Decidir: if / else Visto em aula · 13/08

Repetir: for e while Visto em aula · 13/08

Na aula o i foi declarado fora do for (int i = 0; lá em cima), que é o jeito do C mais antigo. Os dois jeitos funcionam.

E um for dentro de outro for? -> laço aninhado. Se cada um dá n voltas, o de dentro roda n × n vezes. Guarda isso: é o motivo do Bubble Sort ser lento (Módulo 1).

Vetor = fileira de armários numerados Visto em aula · 13/08

Função = máquina com entrada e saída Visto em aula · 13/08

Passou um int pra função? -> ela recebe uma fotocópia. Mexeu na cópia, o original nem fica sabendo. Com vetor é diferente: a função mexe no vetor original. Por quê? -> Módulo 4 (spoiler: ponteiro, que a gente usa sem saber).

Números aleatórios e constantes Visto em aula · 13/08

Na aula foi #define tamanho 100 e srand(time(0)). Mesma coisa: time(0) e time(NULL) são iguais.

Textos (strings) Visto em aula · 13/08

Texto em C = vetor de char que termina com um caractere invisível, o '\0'. Logo, char nome[50] cabe 49 letras (uma vaga é do '\0').

Módulo 1Big O: medir o esforço de um algoritmo

Como descobrir o Big O olhando o código No material do professor

Olha pros laços. É quase sempre isso:

Tá, mas por que isso importa? -> os números No material do professor

Rodei o programa da questão 1 pra montar este guia. Olha o que deu:

Melhor, médio e pior caso No material do professor

O mesmo algoritmo trabalha mais ou menos dependendo de como os dados chegam. Banana na primeira caixa -> melhor caso, 1 passo. Banana na última, ou nem existe -> pior caso, n passos. Prova falou só "a complexidade de X"? -> quase sempre quer o pior caso.

Três palavras que caem em prova No material do professor

• Estável -> se dois têm a mesma chave, continuam na ordem em que chegaram. Ana e Bia com nota 8, Ana antes -> estável mantém Ana antes de Bia.
• In-place (no lugar) -> ordena dentro do próprio vetor, sem criar outro do tamanho n. Merge Sort não é: precisa de vetor auxiliar.
• Comparação × troca -> comparar é perguntar "esse é maior que aquele?"; trocar é mudar os dois de lugar. São contadores diferentes na questão 1.

Módulo 2Ordenações simples: Bubble, Selection e Insertion

Ordenar = deixar crescente: v[0] ≤ v[1] ≤ … ≤ v[n-1]. Os três daqui são fáceis de escrever e lentos pra muito dado (O(n²)). Vou usar sempre o mesmo vetor [7, 3, 5, 2] pra dar pra comparar.

Bubble Sort: as bolhas sobem Visto em aula · 13/08

No exemplo -> 6 comparações e 5 trocas. Já ordenado? -> uma passada sem troca e para: O(n). Ordem decrescente? -> O(n²). E é estável.

Selection Sort: escolher o menor No material do professor

No exemplo -> 6 comparações e só 1 troca. Faz sempre n(n−1)/2 comparações, tando ordenado ou não -> O(n²) no melhor, médio e pior. Não é estável: a troca "de longe" pode passar um igual na frente do outro.

Insertion Sort: arrumar carta na mão No material do professor

No exemplo -> 6 comparações e 5 movimentações. Já ordenado? -> O(n), uma comparação por carta. Pior caso -> O(n²). É estável e é o melhor dos três quando o vetor já tá quase ordenado.

No AulaOrdenacao.c do professor tá no jeito compacto: while (j >= 0 && v[j] > chave). A ordem importa -> primeiro testa j >= 0, senão acessaria v[-1] e dá pau.

Resumo dos três

Módulo 3Recursão, Quick Sort e Merge Sort

Recursão: função que chama ela mesma No material do professor

Quick Sort: escolhe um pivô e separa No material do professor

Imagina o seguinte -> particionamento (Lomuto) em [7, 3, 5, 2, 6, 4], pivô = 4:

Agora ordena [3, 2] e [7, 6, 5] do mesmo jeito. O 4 nunca mais se mexe.

Custo: pivô caindo perto do meio -> log n níveis com n comparações cada -> O(n log n). Mas se o pivô for sempre o maior ou o menor (vetor já ordenado, com pivô no último) -> um lado fica vazio -> O(n²). Não usa vetor auxiliar, mas a recursão gasta memória de pilha. Não é estável.

Merge Sort: divide e intercala No material do professor

Intercalando [3, 7] com [2, 5] -> 3 × 2, pega 2. 3 × 5, pega 3. 7 × 5, pega 5. Sobrou o 7, copia. Deu [2, 3, 5, 7].

Custo: O(n log n) sempre (melhor, médio e pior), porque divide sempre ao meio, não importa o valor de ninguém. O preço -> vetor auxiliar de tamanho n, O(n) de memória extra. É estável.

Quick × Merge

Programa completo da questão 1

Junta os 5 algoritmos (com as funções aí de cima), gera N números aleatórios com malloc, roda cada um numa cópia do mesmo vetor original e mostra os contadores. Sem compilador? -> cola no OnlineGDB.

Saída real com N = 10 (os seus números mudam, o vetor é aleatório):

Original:  467 103 223 436 266 753 489 370 124 226
Bubble     comparacoes:         44   trocas/mov.:         23
Insertion  comparacoes:         31   trocas/mov.:         23
Selection  comparacoes:         45   trocas/mov.:          7
Quick      comparacoes:         19   trocas/mov.:         13
Merge      comparacoes:         21   trocas/mov.:         34

Módulo 4Ponteiros e memória dinâmica

Memória estática × dinâmica Visto em aula · 20/08

• Estática -> tamanho decidido quando você escreve o código: int v[100];. Compilou, é 100 e acabou. Precisou de 101? Ferrou.
• Dinâmica -> alocada em tempo de execução. O programa pergunta pro usuário quanto precisa e pede pro SO na hora. A lista inteira gira em torno disso ("o programa não poderá utilizar um vetor de tamanho fixo").

Ponteiro: o número da casa Visto em aula · 20/08

Aí em cima -> x mora na casa 1000 e guarda 10. p mora na casa 2000 e guarda o número 1000, ou seja, "aponta pra" x.

Por que declaro com tipo (int *, float *, double *)? -> porque o ponteiro precisa saber o que tem lá na casa: quantos bytes ler e quanto andar no p++. Mas o ponteiro em si não gasta o mesmo que o que ele aponta. Ele é só endereço -> tamanho fixo, 8 bytes num PC 64 bits (4 bytes em 32 bits), aponte ele pra char ou pra double.

Por que a função trocar precisa de ponteiro No material do professor

Passou variável comum pra função? -> ela recebe fotocópia. Troca as cópias, os originais ficam iguaizinhos. Passou o endereço? -> a função vai até a casa original e troca lá. É o swap(int* a, int* b) do AulaOrdenacao.c.

E é assim que uma função "devolve" mais de um resultado: void maior_menor(int *v, int n, int *maior, int *menor) escreve nos dois endereços que recebeu.

Vetor é deslocamento de ponteiro: p[i] é *(p + i) Visto em aula · 20/08

Os colchetes parecem um negócio separado, mas não são -> p[i] é só escrita bonita pra *(p + i): o + calcula o endereço do elemento i, o * vai lá e pega o conteúdo. O nome do vetor é o endereço do primeiro armário. Por isso, passou vetor pra função -> ela mexe no original.

p++ anda um pra frente. Posso voltar? -> pode, p--. O que não pode é perder a referência do começo do bloco -> aí depende do dev, não da linguagem.

malloc e free: pedir e devolver memória Visto em aula · 20/08

Lixo de memória (vazamento): se o p passar a apontar pra outro lugar antes do free, aquele bloco fica reservado e ninguém mais acha ele -> não dá pra limpar. Faz isso num laço e o programa vai comendo memória (o Chrome que o diga).

realloc: aumentar ou encolher o bloco Não visto em aula · a lista cobra (questão 3)

A questão 3 pede remover valores "redimensionando a região de memória quando necessário". Isso é o realloc. Imagina o seguinte -> você tem um bloco de n ints e agora só precisa de k. realloc(v, k * sizeof(int)) -> "SO, muda meu terreno pra esse tamanho e leva a mobília junto". Ele mantém os dados que cabem e devolve o endereço novo (pode mudar de lugar!).

Por que o ponteiro novo, e não v = realloc(v, …) direto? -> se o realloc falhar, ele devolve NULL. Aí você sobrescreveu o v com NULL e perdeu o único endereço do bloco antigo -> lixo de memória, olha ele de novo.

As operações da questão 3, uma por uma Ponteiros: 20/08Remover com realloc: não visto

Maior e menor: começa supondo que o primeiro é o maior e o menor, percorre o resto atualizando. Média: soma tudo e divide por n, convertendo pra double antes (senão divisão inteira corta as casas).

Inverter sem outro vetor: um ponteiro no começo, outro no fim. Troca, anda os dois pro meio, para quando se cruzarem.

Remover todas as ocorrências de um valor: dois índices. O i lê todo mundo; o k marca onde escrever o próximo que fica. No fim, k é o tamanho novo -> realloc encolhe o bloco.

Rodando com 4 9 4 1 7 4 e removendo o 4:

Maior: 9 | Menor: 1 | Media: 4.83
Invertido: 4 7 1 4 9 4
Depois de remover (3 elementos): 7 1 9

Módulo 5Struct e buscas (sequencial e binária)

struct = ficha de cadastro Visto em aula · 13/08

E se eu quiser juntar as variáveis num tipo só? -> struct -> registro -> conjunto de variáveis de tipos diferentes. É um modelo: cria uma vez, usa quantas fichas quiser.

Do jeito que foi na aula (struct.c, 13/08):

Com typedef (jeito do material do professor) você dá um apelido e para de escrever struct toda hora. Os dois jeitos valem na prova:

Vetor de fichas com malloc Visto em aula · struct 13/08 + malloc 20/08

A aula fez aluno[10] fixo. A lista quer alocado dinamicamente -> junta as duas aulas:

Busca sequencial: lista de chamada Não visto em aula · a lista cobra

Busca binária: adivinha o número No material do professor

Procurando o RA 5030 no vetor ordenado:

3050 < 5030 -> tudo à esquerda do meio vai pro lixo. Na 2ª olhada, achou. A sequencial ia precisar de 6.

Por que a binária exige vetor ordenado (a lista pede pra demonstrar) No material do professor

Mesmo RA 5030, agora no vetor desordenado. Ele tá na posição 0.

O meio é 2040. Como 2040 < 5030, a busca conclui que o 5030 "só pode estar à direita" -> joga fora a esquerda, onde ele tava de verdade. Resultado: "não encontrado", com o aluno cadastrado lá. Logo, descartar metade só vale se a ordem garantir que tudo à esquerda é menor.

Ordenar os alunos pelo RA No material do professor

Qualquer ordenação serve; aqui foi Insertion. O ponto crítico -> mover a struct inteira. Trocou só os RAs? -> o RA de um aluno fica com o nome e a nota de outro. Bagunça total.

Programa completo da questão 2

--- Vetor DESORDENADO, buscando RA 5030 ---
[sequencial] encontrado com 1 comparacoes: RA 5030 | Ana      | nota 8.5
[binaria] NAO encontrado (3 comparacoes)
--- Vetor ORDENADO por RA ---
[sequencial] encontrado com 6 comparacoes: RA 5030 | Ana      | nota 8.5
[binaria] encontrado com 2 comparacoes: RA 5030 | Ana      | nota 8.5

Módulo 6Tabela hash

Função hash No material do professor

No hash_vetor.c e no tabela_hash_encadeamento.c do professor é exatamente isso: chave % 10. Boa função hash -> rápida e espalha as chaves. Tamanho primo (11, 13) costuma espalhar melhor que 10.

Colisão: dois na mesma gaveta No material do professor

101 e 111 dão resto 1 -> os dois querem o escaninho 1. Isso é colisão, e não tem como fugir: tem muito mais código possível do que gaveta. A lista exige tratar, com uma de duas estratégias:

Estratégia 1: encadeamento (lista em cada gaveta) No material do professor

Lembra da aula de 20/08, "um ponteiro que aponta pra outro ponteiro numa lista"? -> é isso aqui: lista encadeada. Cada nó é uma struct com os dados e um ponteiro pro próximo nó. Vantagem -> guarda valores sem precisar de um bloco grande contínuo, e percorre a lista seguindo os ponteiros.

Pra percorrer uma gaveta -> começa em tabela[g] e segue atual = atual->proximo até dar NULL. Pra remover um nó do meio -> o anterior "pula" o removido: anterior->proximo = atual->proximo, depois free(atual).

E qual o rolê de uma lista que volta? -> ponteiro pra frente e ponteiro pra trás (proximo e anterior no mesmo nó) -> lista duplamente encadeada. Pra hash não precisa, a simples resolve.

Estratégia 2: endereçamento aberto (sondagem linear) Não visto em aula · opcional: a lista aceita encadeamento

Tudo fica no próprio vetor, sem ponteiro. Detalhe que cai -> ao remover, marca a vaga como "removida" em vez de esvaziar. Esvaziou a vaga 2? -> a busca pelo 121 para nela achando que ele não existe.

Programa completo da questão 4 (encadeamento)

Inserir, pesquisar pelo código, alterar estoque, remover, exibir, com colisão provocada de propósito (101, 111 e 121 caem todos na gaveta 1).

COLISAO: codigo 111 caiu na gaveta 1, que ja tinha itens
COLISAO: codigo 121 caiu na gaveta 1, que ja tinha itens
[0] -> NULL
[1] -> {121, Cafe, 15} -> {111, Acucar, 20} -> {101, Arroz, 50} -> NULL
[5] -> {205, Feijao, 30} -> NULL
[7] -> {37, Leite, 40} -> NULL
Busca 101: Arroz, estoque 50 (3 comparacoes)

Custo: procurar em todos × usar hash No material do professor

Fator de carga α = elementos ÷ gavetas -> tamanho médio de cada corrente. 5 produtos em 10 gavetas -> α = 0,5. Quanto menor o α, mais perto de O(1).

Módulo 7Bônus: os outros quatro da apostila Só na apostila

A lista não pede, mas a apostila do professor traz. Sobrou tempo? -> saiba pelo menos a ideia e o Big O de cada um.

• Shell Sort -> Insertion com "saltos". Primeiro ordena elementos distantes (intervalo n/2, depois n/4…) e termina com intervalo 1, que é um Insertion normal. Pior caso O(n²) com intervalos pela metade. Não é estável.
• Heap Sort -> monta um heap máximo (árvore guardada no vetor em que todo pai ≥ filhos; filhos de i ficam em 2i+1 e 2i+2). Tira o maior da raiz, joga no fim, conserta o heap, repete. O(n log n) no pior caso e memória O(1). Não é estável.
• Counting Sort -> não compara ninguém. Conta quantas vezes cada valor aparece (vetor de contagens de 0 até k−1) e usa as somas acumuladas pra posicionar. O(n + k). Só serve pra inteiro num intervalo pequeno. Estável.
• Radix Sort -> ordena dígito por dígito, das unidades pras centenas, com uma ordenação estável (Counting) em cada passada. O(d·(n + b)), com d dígitos e base b. Estável.

* A apostila observa que, com todas as chaves iguais, a versão dela do Heap Sort termina em O(n).

Módulo 8Na hora da prova

Esqueleto pra começar qualquer questão

Checklist antes de entregar

• Todo malloc tem teste de NULL e um free no fim.
• Função fora do main, e mexendo no parâmetro dela (não na variável do main). Foi o erro do teste.c.
• Laço de 0 até < n. Nada de v[n].
• Cada ordenação roda numa cópia do vetor original, com os contadores zerados antes.
• Quick e Merge -> chamada inicial com 0 e n - 1. Caso base inicio < fim.
• Busca binária -> vetor ordenado antes. meio = inicio + (fim - inicio) / 2. Laço while (inicio <= fim).
• Texto -> strcpy pra copiar, strcmp pra comparar. Nada de = ou == em texto.
• Struct por ponteiro usa ->; struct direta usa ..
• Hash -> trata código negativo; remove com o ponteiro anterior; libera cada nó.

Perguntas teóricas prováveis, com resposta curta