# Lista Etapa 2 - Parte 1 (AED)

**1) a)** - É uma estrutura que é sequencial, só pode ir para uma direção seguindo uma ordem linear.
**b)**
- Pilha - A pilha é uma é uma estrutura de dados linear que funciona como uma pilha de pratos, onde você coloca um prato no topo e retira sempre o prato que está no topo.
- Fila - É uma estrutura que segue uma ordem em que o primeiro elemento inserido é o primeiro a ser removido.
- Lista - A lista é uma estrutura de dados linear que armazena uma sequência de elementos de forma ordenada, permitindo inserções, remoções e acessos de elementos em qualquer posição.

**c)**
- Pilha :
- Inserir - O(n) ou O(1)
- Remover - O(1)
- Pesquisar - O(1)
- Fila:
- Inserir - O(1)
- Remover - O(1)
- Pesquisar - O(n)
- Lista:
- Inserir - O(n)
- Remover - O(n)
- Pesquisar - O(n)

**d)**
- Arrays:
- Vantagens: acesso rápido, eficiência em espaço e desempenho.
- Desvantagens: tamanho fixo, inserções/remoções caras.
- Collections:
- Vantanges: tamanho dinâmico, facilidade de uso, menos erros de gerenciamento de memória.
- Desvantagens: sobrecarga de memória/tempo, desempenho variável.

---
**2) a)** Fornece conhecimento sobre eficiência no processamento de dados, desempenho e complexidade, e uma base para entender algoritmos mais complexos.

**b)** Complexidade de tempo e espaço, estabilidade, facilidade de implementação e manutenção.

**c)** é um algoritmo de ordenação que não exige espaço adicional significativo além do que já é necessário para armazenar a entrada original.

**d)** Um algoritmo de ordenação estável é o que mantém a ordem relativa dos elementos que são iguais no conjunto de dados. Ou seja, quando dois elementos possuem o mesmo valor, a ordem de inserção desses elementos no conjunto original é preservada após a ordenação. Como exemplo podemos citar o MergeSort.

**e)**
- Ordenação interna: Ocorre quando todos os dados a serem ordenados cabem na memória principal (RAM). O algoritmo pode operar diretamente sobre os dados, sem a necessidade de acessar dispositivos de armazenamento externo.
- Ordenação externa: É usada quando o volume de dados a ser ordenado é maior que a capacidade de memória RAM disponível. Nesse caso, o algoritmo precisa acessar dispositivos de armazenamento externo, como SSDs, para ordenar os dados.

**f)** C(n) representa o número de comparações realizadas pelo algoritmo de ordenação para ordenar um conjunto de n elementos, já o M(n) representa o número de movimentações ou trocas de elementos realizadas pelo algoritmo de ordenação.

**g)** Esses valores se referem ao nível de complexidade do algoritmo.

---

**3) a)**
- No Bubblesort o algoritmo percorre repetidamente o vetor, comparando pares de elementos adjacentes.
- O Selection Sort é um algoritmo simples que seleciona o menor (ou maior) elemento da lista e o coloca na posição correta.
- O Insertion Sort é um algoritmo simples que constrói a lista ordenada um item de cada vez, inserindo o item correto na posição certa, em um vetor parcialmente ordenado.
- O QuickSort escolhe um "pivô" no vetor e divide o vetor em duas partes: uma contendo elementos menores que o pivô e outra com elementos maiores. Essas duas partes são então ordenadas recursivamente.
**b)** 

**c)** Estabilidade dos algoritmos:
- Estáveis: BubbleSort, InsertionSort e MergeSort.
- Não estáveis: SelectionSort e QuickSort.

---

**4) a)** A pesquisa simples (ou pesquisa linear) é o método mais básico de pesquisa em que o algoritmo percorre todos os elementos de uma lista ou vetor, um por um, até encontrar o item desejado ou até que todos os elementos tenham sido verificados. Pode ser usado em listas não ordenadas, em pequenos conjuntos de dados e quando a ordenação não é uma prioridade.
**b)** A pesquisa binária é um método eficiente para buscar um item em uma lista ordenada. Ela segue o princípio da divisão e conquista, reduzindo o espaço de busca pela metade a cada comparação. O algoritmo compara o item desejado com o elemento do meio da lista e decide se deve procurar na metade inferior ou superior da lista, repetindo esse processo recursivamente. Pode ser usado em listas ordenadas, grandes conjuntos de dados e quando a perfomance é crítica.

---

**5)**

 static int pesquisaSimples(int[] v, int n, int chave) {
        for (int i = 0; i < n; i++)
            if (v[i] == chave) return i;
        return -1;
    }

---

**6)**

public int pesquisaBinaria(int[] v, int n, int chave)
{
    int inicio = 0;
    int fim = n - 1;

    while (inicio <= fim)
    {
        int meio = inicio + (fim - inicio) / 2;
        if (v[meio] == chave)
            return meio;

        if (v[meio] < chave)
            inicio = meio + 1;
        else fim = meio - 1;
    }

    return -1;
}

---

**7)** A notação C(n) representa o custo de uma operação de pesquisa sequencial em uma lista de tamanho n, ou seja, quantas comparações o algoritmo realiza para encontrar o item procurado.
Melhor Caso (C(n) = 1) (1° posição)
Pior Caso (C(n) = n) (última posição ou não está na lista)
Caso Médio (C(n) = (n + 1) / 2) (está em uma posição aleatória)

---

**8)**

**A)** A função M realiza uma pesquisa binária em um vetor X ordenado. Ela procura um valor K no vetor X que possui N elementos.

**B)**
1. pivo é calculado como o índice central do vetor, sendo i = 0 e j = 6
2. No primeiro cálculo, pivo = (0 + 6) / 2 = 3, e v[3] = 19. Como 80 > 19, i é atualizado para pivo + 1 = 4.
3. No segundo cálculo, pivo = (4 + 6) / 2 = 5, e v[5] = 80, que é o valor buscado (k=80).
4. A função retorna o índice 5, indicando que 80 foi encontrado na posição 5 do vetor.

**C)**
1. A busca binária começa com i=0 e j=6.
2. pivo inicialmente é 3, e v[3] = 19. Como 12 < 19, j é atualizado para pivo - 1 = 2.
3. No próximo cálculo, pivo = (0 + 2) / 2 = 1, e v[1] = 8. Como 12 > 8, i é atualizado para pivo + 1 = 2.
4. pivo é recalculado como 2, e v[2] = 11. Como 12 > 11, i é atualizado para pivo + 1 = 3.
5. Agora, i=3 e j=2, o que termina o while. Como 12 não foi encontrado, a função retorna -1.

**D)**

1. pivo começa como 3, e v[3] = 9. Como 32 > 9, i é atualizado para pivo + 1 = 4.
2. pivo é então calculado como 5, e v[5] = 23. Como 32 > 23, i é atualizado para pivo + 1 = 6.
3. pivo é agora 6, e v[6] = 77. Como 32 < 77, j é atualizado para pivo - 1 = 5.
4. O while termina sem encontrar 32, e a função retorna -1, mesmo que 32 esteja presente no vetor. Isso ocorre porque o vetor não está ordenado.

**E)**

public int M<T>(T[] x, int n, T k) where T : IComparable<T>
{
    int i = 0, j = n - 1, pivo = 0;

    do
    {
        pivo = (i + j) / 2;
        if (k.CompareTo(x[pivo]) > 0)
            i = pivo + 1;
        else
            j = pivo - 1;
    }
    while (x[pivo].CompareTo(k) != 0 && i <= j);

    if (x[pivo].CompareTo(k) == 0)
        return pivo;

    return -1;
}

---

**9) a)** Falso. O algoritmo quickSort tem essa complexidade apenas no melhor e médio caso, no pior caso sua complexidade é O(n²).
**b)** Verdadeiro.
**c)** Falso. Um algoritmo com O(n²) não pode ser considerado melhor que um com O(n), pois o primeiro cresce muito mais rapidamente à medida que o tamanho de n aumenta.

---

**10)**

Primeira Partição:

Pivô: A
Após reorganizar, resultado: A B U M C K R
Segunda Partição (B U M C K R):

Pivô: R
Resultado: A B M C K R U
Terceira Partição (B M C K):

Pivô: K
Resultado: A B C K M R U
Quarta Partição (B C):

Pivô: C
Resultado: A B C K M R U

A sequência ordenada é: A B C K M R U.

---

**11) a)** Top-Down (Quicksort): Começa com o problema inteiro e divide recursivamente até chegar a subproblemas triviais. A ordenação é feita enquanto o algoritmo recursivo vai "subindo" das divisões.
Bottom-Up (MergeSort): Começa com os subproblemas triviais e vai "construindo" a solução final de forma iterativa, fundindo sublistas até que se obtenha a lista ordenada.
**b)** A estratégia "dividir para conquistar" consiste em dividir o problema em subproblemas menores, resolvê-los e depois combinar as soluções, sendo uma técnica fundamental para melhorar a eficiência de algoritmos como MergeSort e QuickSort.

---

**12)** C.

---

**13)** B.

---

**14)** D.

---

**15)** A.

---

**16)** A escolha do pivô pode ser feita de diversas maneiras. A forma mais comum é o pivô na mediana, que ocorre somando o primeiro índice com o último e dividindo o resultado por 2. A eficiência do QuickSort depende fortemente de como o pivô divide a lista. O ideal é que o pivô divida a lista em duas sublistas aproximadamente iguais. Quando isso ocorre, o algoritmo tem uma complexidade O(n log n).

---

**17)** A.

---

**18)** A.

---

**19)** O HeapSort é um algoritmo de ordenação eficiente baseado em uma estrutura de dados chamada heap. O HeapSort é um algoritmo eficiente de ordenação, particularmente quando a memória é um recurso limitado, já que é um algoritmo in-place. Sua complexidade no pior caso é O(n log n), o que o torna robusto para arrays grandes. No entanto, ele não é estável e pode ser mais lento que outros algoritmos como o QuickSort em algumas situações práticas.