---
# System prepended metadata

title: 2022-10-27 edb1 anotações de aula
tags: [edb1]

---

---
breaks: false
tags: edb1
title: '2022-10-27 edb1 anotações de aula'
---
# EDB1 - anotações de aula

Algoritmos de ordenação.

- 2u:
    - Bubble sort
- 3u:
    - outros

O bubble sort faz varredura por toda a série.

É ineficiente

$O(N^2)$.

Nele, há:
- comparação (entre pares de valores)
- ordenação

## Comparação
O modo ineficiente é, para cada elemento, comparar com todos os outros (`for` dentro de `for`).

A fase de comparação pode ser:
- por loop aninhado (ineficiente)
- por loop único com verificação do próximo elemento (otimizado)
- por recursão (reduzindo o tamanho da série) e comparando sempre o 1o e o 2o elementos.

O custo dessa verificação é linear. No pior caso, será $O(N)$.

## Ordenação

Maneiras de implementar:
<!-- - por loop aninhado (ineficiente) -->
- por loop único com verificação do próximo elemento (otimizado)
    - compara 2 elementos:
        - se posterior menor, troca
        - se posterior maior, ignora
- por recursão (reduzindo o tamanho da série) e comparando sempre o 1o e o 2o elementos.

```c
#include <stdio.h>

void troca(char *v, int i, int j) {
    char aux;
    aux = v[i];
    v[i] = v[j];
    v[j] = aux;
}

void sort(char *v, int N) {
    int conflito;
    do {
        conflito = 0;
        for (int i = 0; i < N - 1; i++) {
            if (v[i + 1] < v[i]) {
                troca(v, i, i + 1);
                conflito = 1;
            }
        }
    } while (conflito == 1);
}

int main() {
    int serie = {4, 7, 1, 9, 2, 8, 3}; // exemplo (a)
    sort(serie, 7);
    return 1;
}
```

**Exemplos**: ordenar as séries

### a) `{4, 7, 1, 9, 2, 8, 3}`

### b) `{1,-1,2,7,4,9,3,5,0}`

| troca| do  | for | 0    | 1    | 2   | 3   | 4   | 5   | 6   | 7   | 8   |
| ---- | --- | --- | ---- | ---- | --- | --- | --- | --- | --- | --- | --- |
| 0    | 0   | -   | 1    | -1   | 2   | 7   | 4   | 9   | 3   | 5   | 0   |
| 1    |     | 0   | [1]  | [-1] | 2   | 7   | 4   | 9   | 3   | 5   | 0   |
|      |     |     | [-1] | [1]  | 2   | 7   | 4   | 9   | 3   | 5   | 0   |
| 2    |     | 1   | -1   | 1    | 2   | [7] | [4] | 9   | 3   | 5   | 0   |
|      |     |     | -1   | 1    | 2   | [4] | [7] | 9   | 3   | 5   | 0   |
| 3    |     | 2   | -1   | 1    | 2   | 4   | 7   | [9] | [3] | 5   | 0   |
|      |     |     | -1   | 1    | 2   | 4   | 7   | [3] | [9] | 5   | 0   |
| 4    |     | 3   | -1   | 1    | 2   | 4   | 7   | 3   | [9] | [5] | 0   |
|      |     |     | -1   | 1    | 2   | 4   | 7   | 3   | [5] | [9] | 0   |
| 5    |     | 4   | -1   | 1    | 2   | 4   | 7   | 3   | 5   | [9] | [0] |
|      |     |     | -1   | 1    | 2   | 4   | 7   | 3   | 5   | [0] | [9] |
| 6    | 1   | 0   | -1   | 1    | 2   | 4   | [7] | [3] | 5   | 0   | 9   |
|      |     |     | -1   | 1    | 2   | 4   | [3] | [7] | 5   | 0   | 9   |
| 7    |     | 1   | -1   | 1    | 2   | 4   | 3   | [7] | [5] | 0   | 9   |
|      |     |     | -1   | 1    | 2   | 4   | 3   | [5] | [7] | 0   | 9   |
| 8    |     | 2   | -1   | 1    | 2   | 4   | 3   | 5   | [7] | [0] | 9   |
|      |     |     | -1   | 1    | 2   | 4   | 3   | 5   | [0] | [7] | 9   |
| 9    | 2   | 0   | -1   | 1    | 2   | [4] | [3] | 5   | 0   | 7   | 9   |
|      |     |     | -1   | 1    | 2   | [3] | [4] | 5   | 0   | 7   | 9   |
| 10   |     | 1   | -1   | 1    | 2   | 3   | 4   | [5] | [0] | 7   | 9   |
|      |     |     | -1   | 1    | 2   | 3   | 4   | [0] | [5] | 7   | 9   |
| 11   | 3   | 0   | -1   | 1    | 2   | 3   | [4] | [0] | 5   | 7   | 9   |
|      |     |     | -1   | 1    | 2   | 3   | [0] | [4] | 5   | 7   | 9   |
| 12   | 4   | 0   | -1   | 1    | 2   | [3] | [0] | 4   | 5   | 7   | 9   |
|      |     |     | -1   | 1    | 2   | [0] | [3] | 4   | 5   | 7   | 9   |
| 13   | 5   | 0   | -1   | 1    | [2] | [0] | 3   | 4   | 5   | 7   | 9   |
|      |     |     | -1   | 1    | [0] | [2] | 3   | 4   | 5   | 7   | 9   |
| 14   | 6   | 0   | -1   | [1]  | [0] | 2   | 3   | 4   | 5   | 7   | 9   |
|      |     |     | -1   | [0]  | [1] | 2   | 3   | 4   | 5   | 7   | 9   |
| Last | 7   | 0   | -1   | 0    | 1   | 2   | 3   | 4   | 5   | 7   | 9   |

## conteúdo avaliação
- tipo abstrato de dados
- busca linear
- busca binaria
- analise de complexidade de algoritmos
- algoritmo de orgenação por bolha (bubble sort)