Analise de Algoritmos de Ordenacao - Mergesort InserctionSort Recursivo e Quicksort

Suponha que você foi contratado como DesenvolvedorEngenheiro de Software da Guuglu uma máquina de busca que pode ser utilizada para realizar pesquisas na internet Sua função é realizar alguns testes para verificar a eficiência de ordenação de valores que representam índices de chaves de busca que ficam registrados na memória principal do servidor Neste trabalho você deverá utilizar dois algoritmos de ordenação Você pode utilizar um código pronto já disponível na internet ou implementar sua própria versão Você deverá também utilizar a função de complexidade do algoritmo calculada pela resolução da sua relação de recorrência este cálculo já foi mostrado em sala de aula Para realizar a comparação você deverá adicionar um contador para contar o número de trocas de elementos no vetor Neste sentido os testes devem ser feitos com três algoritmos Mergesort Sua ordem de complexidade pode ser definida pela relação de recorrência aproximada Tn 2Tn2 n T1 0 InserctionSort Recursivo algoritmo disponível no final deste arquivo Sua ordem de complexidade pode ser definida pela relação de recorrência aproximada Tn Tn 1 n T1 1 Quicksort Neste caso você deverá pesquisar e mostrar a Relação de Recorrência e seu resultado não precisa mostrar a resolução apenas o resultado para o caso médio do algoritmo não considerar o pior caso pois isto é muito raro neste algoritmo Tendo os códigos em mãos você deverá rodar os processos com diferentes entradas Para cada entrada você deverá contar o número de comparações que o algoritmo faz adicionando um contador no código da ordenação além de cronometrar o tempo do processo Utilizar a mesma entrada para todos os métodos Portanto para realizar os testes você deverá gerar vetores com valores aleatórios Desta forma para cada um dos métodos você deverá montar uma tabela comparativa com a seguinte configuração Tamanho da Entrada Número de Comparações esperadas conforme Complexidade Calculada Número de Comparações Alcançadas Tempo gasto no processamento 10 50 100 1000 10000 100000 A tabela deverá ser preenchida conforme os resultados alcançados nos experimentos Além disso você deverá montar gráficos para comparar os resultados dos algoritmos testados de forma visual levar em consideração o número de comparações efetuadas no gráfico Parte 2 do trabalho Gerar um vetor de números aleatórios com pelo menos 16 elementos e desenhe a árvore de chamadas do Mergesort Conte o número de trocas que serão feitas Informe o número contado e compare com a ordem de complexidade calculada pela relação de recorrência do mergesort Exemplo de desenho Insertion Sort Número de Comparações em função de n On2 Tamanho da Entrada Número de Comparações esperadas conforme Complexidade Calculada Número de Comparações Alcançadas Tempo gasto no processamento μs 10 100 45 6 50 2500 1225 72 100 10000 4950 170 1000 1000000 499500 7522 10000 100000000 49995000 50691 100000 10000000000 4999950000 4494638 Merge Sort Número de comparações esperadas Onlgn Tamanho da Entrada Número de Comparações esperadas conforme Complexidade Calculada Número de Comparações Alcançadas Tempo gasto no processamento μs 10 34 23 19 50 283 224 105 100 665 539 79 1000 9966 8727 746 10000 132878 120517 1182 100000 1660964 1536138 18525 Quick Sort Relação de recorrência para caso médio Resultado Número de comparações esperadas Onlgn Tamanho da Entrada Número de Comparações esperadas conforme Complexidade Calculada Número de Comparações Alcançadas Tempo gasto no processamento μs 10 34 54 6 50 283 436 40 100 665 1067 38 1000 9966 17057 715 10000 132878 209268 1781 100000 1660964 2505158 9028 Quick Sort y número de comparações n tamanho da entrada Árvore do Merge Sort Código fonte 1 import javaioFile Import the File class 2 import javautilScanner Import the Scanner class to read text files 3 import javaioFileNotFoundException Import this class to handle errors 4 5 public class Main 6 public static long cmp 0 7 public static void mainString args 8 int tamanhos 10 50 100 1000 10000 100000 9 int teste new int10 new int50 new int100 new int1000 new int10000 new int100000 10 int copia new int10 new int50 new int100 new int1000 new int10000 new int100000 11 try 12 for int i 0 i 6 i 13 File myObj new Filetamanhosi txt 14 Scanner myReader new ScannermyObj 15 int n myReadernextInt 16 for int j 0 j n j 17 int valor myReadernextInt 18 testeij valor 19 copiaij valor 20 21 myReaderclose 22 23 catch FileNotFoundException e 24 SystemoutprintlnAn error occurred 25 eprintStackTrace 26 27 28 for int i 0 i 6 i 29 long startTime SystemnanoTime 30 cmp insertionSorttestei 31 long elapsedTime SystemnanoTime startTime 32 SystemoutprintlnTotal execution time microssegundos 33 elapsedTime1000 34 SystemoutprintlnComparacoes insertionSort cmp 35 36 for int j 0 j testeilength j testeij copiaij 37 38 startTime SystemnanoTime 39 cmp mergeSorttestei 0 testeilength 1 40 elapsedTime SystemnanoTime startTime 41 SystemoutprintlnTotal execution time microssegundos 42 elapsedTime1000 43 SystemoutprintlnComparacoes mergeSort cmp cmp 0 for int j 0 j testeilength j testeij copiaij startTime SystemnanoTime quickSorttestei 0 testeilength1 elapsedTime SystemnanoTime startTime SystemoutprintlnTotal execution time microsegundos elapsedTime1000 SystemoutprintlnComparacoes quickSort cmp public static long insertionSortint v long cmp 0 for int i 0 i vlength i for int c i c 0 c if vc1 vc int aux vc1 vc1 vc vc aux cmp return cmp public static long mergeint arr int l int m int r int cmp 0 int n1 m l 1 int n2 r m int L new intn1 int R new intn2 for int i 0 i n1 i Li arrl i for int j 0 j n2 j Rj arrm 1 j cmp if Li Rj arrk Li i else arrk Rj j k while i n1 arrk Li i k while j n2 arrk Rj j k return cmp public static long mergeSortint arr int l int r long cmp 0 if l r int m l r l 2 cmp mergeSortarr l m cmp mergeSortarr m 1 r cmp mergearr l m r return cmp public static void printArrayint arr int n arrlength for int i 0 i n i Systemoutprintarri Systemoutprintln public static void quickSortint v int ini int fim if fim ini 1 1 return int i ini int j fim int pivo vini fim2 while i j while vi pivo i cmp cmp while vj pivo j cmp cmp if i j int aux vi vi vj vj aux i j cmp if j ini quickSortv ini j if i fim quickSortv i fim