Geração Aleatória de Chaves e Registros com Ordenação Bubble Sort em C++ - Projeto DAOO

Projeto 2 DAOO Etapa 1 Rotina de Geração Aleatória do Vetor de Chaves a Criar uma função para gerar e retornar um vetor com as chaves números inteiros Utilizar a classe vector do C para armazenar e retornar as chaves O protótipo da função deve ser vectorint rotinagerachavesint nkey int keyrange b A função deve receber a quantidade de chaves nkey e a faixa de valores keyrange na qual as chaves devem ser geradas Observe que keyrange deve ser maior ou igual a nkey keyrange nkey Por exemplo podemos pedir para gerar nkey100 chaves cujos valores das chaves devem estar entre 1 e 1000 ou seja keyrange1000 Utilizar a função rand para implementar esta rotina c As chaves geradas não podem ter valores repetidos d Implementar uma função auxiliar para esta rotina com o objetivo de identificar se uma chave sorteada com a função rand já foi gerada anteriormente e armazenada no vetor Se ela já existir o processo de sorteio deve ser repetido até que se encontre uma nova chave O protótipo da função auxiliar deve ser bool chaveexistevectorint vetorchaves int chave int tam A função deve receber o vetor das chaves vetorchaves a chave atual que foi gerada chave e o tamanho atual do vetorchaves retornando true se a chave já existe e false caso contrário Etapa 2 Rotina de Geração da Tabela com as Chaves e Registros a Utilizar a estrutura de Registro struct usada no exemplo da Busca Sequencial Indexada b Criar uma função que recebe o vetor de chaves e preencha a tabela com as chaves e respectivos registros Cada linha da tabela Chave Registro O conteúdo de cada campo do registro também deve ser gerado aleatoriamente e preenchido dentro da função c Utilizar como estrutura de retorno da Tabela de Registros ChaveDados do Produto o tipo vectorRegistro O protótipo da função deve ser vectorRegistro rotinageraregistrosvectorint vetorchaves Etapa 3 Rotina de Ordenação da Tabela a Adaptar a rotina de ordenação Bubble Sort para receber e ordenar o vetor de registros gerado na Etapa 2 O protótipo da função deve ser void ordenacaobubblevectorRegistro x Etapa 4 Adaptar Rotina de Busca Sequencial em Tabela Ordenada a Adaptar a rotina de Busca Sequencial em Tabela Ordenada para operar sobre a tabela de registros ordenada gerada na Etapa 3 contando o número de comparações int buscaSequencialint c vectorRegistro x Etapa 5 Avaliação do Número de Comparações Busca Sequencial em Tabela Ordenada Implementar uma rotina para a Gerar uma tabela de registros com 100 entradas e espaço de chaves entre 1 e 100 b Sortear uma chave de busca dentro da faixa de valores c Realizar a busca e contabilizar o número de comparações para o método Busca Sequencial em Tabela Ordenada d Repetir o procedimento 1000 vezes e calcular o número médio de comparações Etapa 6 Adaptar Rotina de Busca Binaria a Adaptar a rotina de Busca Binaria para operar sobre a tabela de registros ordenada gerada na Etapa 3 contando o número de comparações int BuscaBinariaint chave vectorRegistro vetor int comp Dentro da rotina de busca binária o número de comparações deve ser atualizado na variável comp que foi passada por referência para a função Etapa 7 Avaliação do Número de Comparações Busca Binária Implementar uma rotina para a Gerar uma tabela de registros com 100 entradas e espaço de chaves entre 1 e 100 b Sortear uma chave de busca dentro da faixa de valores c Realizar a busca e contabilizar o número de comparações para o método Busca Binária d Repetir o procedimento 1000 vezes e calcular o número médio de comparações