Análise de Algoritmos de Busca e Ordenação

Este repositório contém o projeto da Unidade I da disciplina de Laboratório de Estrutura de Dados (LEDA) do período 2025.2

---

Objetivo do Projeto

O objetivo principal é desenvolver habilidades de implementação e análise de desempenho de diversos algoritmos de busca e ordenação em Java. O projeto combina complexidade algorítmica e prática experimental, medindo tempos de execução para identificar cenários onde cada algoritmo é mais vantajoso.

---

Algoritmos Implementados

Algoritmos de Busca:

• Busca Linear Iterativa
• Busca Linear Recursiva
• Busca Binária Iterativa
• Busca Binária Recursiva
• Busca Linear Iterativa Duas Pontas

Algoritmos de Ordenação:

Algoritmo	Versões Específicas
BubbleSort	Versão Clássica e Versão Otimizada
SelectionSort	Versão Clássica e Versão Estável
Insertion Sort	Versão Clássica
MergeSort	Versão Clássica e Versão TimSort do Java (.sort() para objetos)
QuickSort	Versão Clássica, Versão Clássica + Shuffle, e Versão do Java (.sort() para inteiros¹)
Counting Sort	Utiliza o campo nota como chave²

[¹] Realizamos experimentos adicionais com as variações do QuickSort em vetores de inteiros para comparar com a implementação híbrida da linguagem. [²] Atributo da classe Estudante.

---

Análise da Performance

A performance de cada algoritmo é medida utilizando "System.nanoTime()".

1. Tamanhos de vetor (n): Medidas em quatro tamanhos
   • Para busca: 10K, 500K, 1M e 1M500K
   • Para ordenação: 10K, 50K, 100K e 200K
2. Cenários de Teste:
   • Para busca: vetores aleatórios.
   • Para ordenação: vetores aleatórios, vetores já ordenados e vetores em ordem inversa.
3. Execuções: Para cada cenário, foram realizadas pelo menos 20 execuções.
4. warm-up: As 5 primeiras execuções serão descartadas, para minimizar a variabilidade da JVM.
5. Independência: A saída ordenada de um algoritmo não deve ser usada como entrada para o próximo, a fim de não distorcer os resultados.

---

Dados utilizados

Para a realização dos experimentos, visto que seria inviável criar manualmente todos os nomes para os objetos do tipo Estudante, fizemos um código simples em Python (gerador_nomes.py) que cria combinações entre nomes pré-definidos e salva-as num arquivo csv. Complementarmente, para fins de usabilidade, criamos um arquivo com 1M e 500K nomes (nomes_1.5M.csv), sendo bem mais que o suficiente para os testes realizados. Ele é utilizado como parâmetro pela classe GeradorDeEstudante.java para criar um array de Estudantes do tamanho desejado. Em relação aos experimentos em array de inteiros, criamos um gerador no próprio código-fonte (GeradorDeNotas.java), o qual gera arrays do tamanho especificado com valores aleatórios de 0 a 10.

---

Resultados obtidos

As médias dos tempos de execução de cada algoritmo, separados por número de elementos (n) e/ou organização do array, encontram-se no diretório results. Disponibilizamos também a planilha com as mesmas tabelas, visando um reaproveitamento ou edição. Vale ressaltar que reconhecemos o nível de imprecisão ao medir o tempo de execução de um algoritmo, por isso, realizamos todos os testes em sequência (divididos em notebooks diferentes) e apenas com a IDE em execução direta. Trabalhando com a média de múltiplos testes (15, descartado o warm-up) percebemos que, de fato, conseguimos resultados mais homogêneos. Entretanto, fatores como hardware, softwares em segundo plano, memória cache e sistema operacional influenciaram e influenciarão os resultados.

---

Integrantes

• Gabriela Andrade (@gabiandradeal)
• Georis Samuel (@georiSamuel)
• Horlan Lacerda (@Horlanlacerda)
• Suelle Maciel (@SuelleMaciel)