---
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.

#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)