Lucas Eduardo, Luís, Paulo Marques e Policarpo
Page 01
HOME SERVICE ABOUT US CONTACT US
• Como funciona: Percorre o vetor da esquerda para a
direita, inserindo cada elemento na posição correta entre
os já ordenados.
• Complexidade:
⚬ Melhor caso: O(n) – vetor já ordenado.
⚬ Pior caso: O(n²) – vetor em ordem decrescente.
⚬ Caso médio: O(n²).
• Vantagens:
⚬ Simples, estável e eficiente para pequenos ou quase
ordenados.
• Desvantagens:
⚬ Ineficiente para grandes vetores desordenados.
Page 02
HOME SERVICE ABOUT US CONTACT US
Page 03
HOME SERVICE ABOUT US CONTACT US
• Como funciona: Utiliza divisão e conquista: divide o vetor
recursivamente, ordena e mescla as partes.
• Complexidade:
-Melhor, pior e médio caso: O(n log n).
-Estável e com desempenho consistente.
• Vantagens:
-Ótimo para grandes volumes de dados.
-Complexidade previsível.
-Ordenação estável.
• Desvantagens:
-Usa memória extra.
-Implementação mais complexa.
-Menos eficiente para vetores pequenos.
Page 02
HOME SERVICE ABOUT US CONTACT US
Page 03
HOME SERVICE ABOUT US CONTACT US
Comparação – Insertion Sort vs Merge Sort
• Insertion Sort:
-Rápido em vetores pequenos ou quase ordenados.
-Desempenho cai de O(n) para O(n²) com dados desordenados.
• Merge Sort:
-Desempenho constante: O(n log n) em todos os casos.
-Melhor escolha para vetores grandes e aleatórios.
Use Insertion Sort para pequenos ou quase ordenados.
Prefira Merge Sort para grandes e desordenados.
Page 02
HOME SERVICE ABOUT US CONTACT US
Algoritmos implementados manualmente:
• Insertion Sort: com laços simples e deslocamento de valores.
• Merge Sort: com chamadas recursivas e vetores auxiliares.
• Testes realizados em vetores de 10.000 a 150.000 números aleatórios e únicos.
• Medições de desempenho com [Link](), repetidas 30 vezes após 10 execuções de
aquecimento (warm-up).
• Resultados salvos em arquivos CSV para análise estatística posterior.
Page 02
• Bibliotecas de importação para criar e escrever em
arquivos de texto, tratar erros de entrada/saída, métodos
utilitários para manipular coleções (listas, conjuntos, etc.),
para armazenar os números antes de escrever no arquivo.
• Classe principal e execução:
1. O método main executa a geração dos arquivos. A
exceção IOException é lançada caso ocorra erro na escrita
de arquivos.
[Link] 15 arquivos, com quantidades de números de 10.000
até 150.000 (multiplicando i de 1 a 15 por 10.000).
[Link] cada quantidade, chama o método gerarArquivo.
• Geração e embaralhamento de lista
1. Cria uma lista de inteiros de 1 até quantidade (sem
repetições).
[Link] a lista com [Link]() para deixá-la
em ordem aleatória.
[Link] um nome como [Link], [Link] etc.,
conforme a quantidade.
[Link] um FileWriter para escrever no arquivo.
[Link] cada número embaralhado em uma nova linha do
arquivo.
Page 03
[Link] o arquivo após a escrita.
• Cria um vetor com 15 tamanhos de vetores: 10.000 a
150.000
• Abre um arquivo CSV para gravar os resultados
• Para cada tamanho de vetor cria um vetor de inteiros
aleatórios e sem repetição.
• Aquecimento para que as medições de tempo fiquem mais
consistentes
• Executa 30 vezes o Insertion Sort, medindo o tempo em
nanossegundos e salvando no CSV.
Page 03
• Verificar se o vetor tem mais de um elemento. Caso
contrário, retorna sem fazer nada, pois um vetor de tamanho
1 já está ordenado.
• Condicional if (esquerda < direita): Isso garante que o vetor
tenha pelo menos dois elementos para continuar a divisão.
Se esquerda >= direita, significa que o vetor não precisa ser
dividido.
• Divisão do vetor: A variável meio calcula o índice do meio do
vetor.
• Recursão: Chama mergeSort duas vezes, uma para a metade
esquerda do vetor (esquerda até meio) e outra para a
metade direita (meio + 1 até direita).
• Merge: Vai dividir o vetor até ele ter apenas um elemento por
vez, chama o método merge para unir as partes já ordenadas.
Page 03