Exercicio insertion sort

387 palavras 2 páginas

Faça vários testes com o objetivo de determinar o comportamento do algoritmo na medida em que a quantidade de elementos do vetor aumenta. Para tanto, considere como operações primitivas, somente a mais significante, no caso as comparações. Inclua um contador para efetuar a quantidade de comparações. Você irá testá-lo de três formas distintas:
- Caso médio: vetor preenchido com números aleatórios
- Melhor caso: vetor preenchido com números em ordem crescente
- Pior caso: vetor preenchido com números em ordem decrescente
Caso Médio: Teste o programa para 50, 100, 200, 400, 800 e 1600 elementos (altere a cada teste o tamanho do vetor). Responda as questões abaixo com o número de comparações realizadas pelo algoritmo a cada teste.
i. ... em um vetor de 50 posições? ->8 ii. ... em um vetor de 100 posições?->8 iii. ... em um vetor de 200 posições?->10 iv. ... em um vetor de 400 posições?->5
v. ... em um vetor de 800 posições?->5 vi. ... em um vetor de 1600 posições?->7
Melhor Caso: Teste o programa para 50, 100, 200, 400, 800 e 1600 elementos (altere a cada teste o tamanho do vetor). Lembre-se de alterar o programa de forma que os elementos do vetor não sejam sorteados (dica: guarde no vetor o próprio valor do índice). Responda as questões abaixo com o número de comparações realizadas pelo algoritmo a cada teste.
i. ... em um vetor de 50 posições?-49 ii. ... em um vetor de 100 posições?-99 iii. ... em um vetor de 200 posições?-199 iv. ... em um vetor de 400 posições?-399
v. ... em um vetor de 800 posições?-799 vi. ... em um vetor de 1600 posições?-1599
Pior Caso: Teste o programa para 50, 100, 200, 400, 800 e 1600 elementos (altere a cada teste o tamanho do vetor). Lembre-se de alterar o programa de forma que os elementos do vetor não sejam sorteados (dica: guarde no vetor o próprio valor do índice em ordem inversa). Responda as questões abaixo com o número de comparações realizadas pelo algoritmo a cada teste.
i. ... em um vetor de 50 posições?-49

Relacionados

Selection Sort
1905 palavras | 8 páginas

Estudo Detalhado do Algoritmo de Ordenação Insertion Sort Gabriela N. Pereira¹, Igor S. O. Lima¹, José Gomes S. Júnior¹, Matheus S. Araújo¹ ¹Curso de Ciência da Computação – Universidade Federal de Alagoas (UFAL) Caixa Postal 61 – 57.600000 – Arapiraca – AL – Brazil {aiuec,igrsme,jnoj,mtesma7}galcm gbnnsc io.ios uir9 ahu.s2,@mi.o Abstract. The purpose of this article is to present a sorting algorithm Insertion Sort, making us reflect on its importance, analyzing it and….

exibir mais
Ética em Pesquisa
1905 palavras | 8 páginas

Estudo Detalhado do Algoritmo de Ordenação Insertion Sort Gabriela N. Pereira¹, Igor S. O. Lima¹, José Gomes S. Júnior¹, Matheus S. Araújo¹ ¹Curso de Ciência da Computação – Universidade Federal de Alagoas (UFAL) Caixa Postal 61 – 57.600000 – Arapiraca – AL – Brazil {aiuec,igrsme,jnoj,mtesma7}galcm gbnnsc io.ios uir9 ahu.s2,@mi.o Abstract. The purpose of this article is to present a sorting algorithm Insertion Sort, making us reflect on its importance, analyzing it and….

exibir mais
Ordenação radix, counting , buket
1202 palavras | 5 páginas

Linear Classificação e Pesquisa de Dados Aula 10 Classificação em Tempo Linear O(n): Counting Sort, Radix Sort e Bucket Sort Algoritmos de classificação em tempo linear exploram determinadas propriedades do conjunto de dados a ser ordenado Principais Algoritmos n n n Counting sort Radix sort Bucket sort 3 UFRGS INF01124 1 Classificação de Dados em Tempo Linear Heapsort e Merge Sort apresentam desempenho de Θ(nlog2n) Quicksort tem custo médio de O(nlog2n) Estes algoritmos se….

exibir mais
COMPUTAÇÃO
312 palavras | 2 páginas

Universidade Estadual da Paraíba Centro de Ciência e Tecnologia Departamento de Matemática, Estatística e Computação Curso de Bacharelado em Computação Professor: Fábio Luiz Leite Jr Aluno (a): Lista de exercícios de revisão 1. Escreva um programa que recebendo um vector de números naturais, os ordene por ordem decrescente tendo como critério o número de ocorrências de cada um no vector. Utilize o seguinte protótipo: void ordenaOcorrencias(int v[], int tamanho); Exemplo: Input: 1 5….

exibir mais
Apredizagem
1441 palavras | 6 páginas

A = 1; *B = 2; } int main() { int X = 0, Y = 0; FuncaoInutil(X, &Y); printf(“%d %d”, X, Y); return 0; } Procedimentos e Funções Exercício 1: Escreva um procedimento ou função em linguagem C que troca dois valores A e B. Exercício 2: Escreva um procedimento ou função em linguagem C que recebe dois valores A e B, calcula a soma e guarda o resultado em A. Exercício 3: Escreva um procedimento ou função em linguagem C que retorna a soma e o produto de dois valores A e B. Procedimentos e Funções….

exibir mais
Ordenação
875 palavras | 4 páginas

ALGORITMOS DE ORDENAÇÃO ORDENAÇÃO POR INSERÇÃO Insertion sort, ou ordenação por inserção, é um simples algoritmo de ordenação, eficiente quando aplicado a um pequeno número de elementos. Em termos gerais, ele percorre um vetor de elementos da esquerda para a direita e à medida que avança vai deixando os elementos mais à esquerda ordenados. O algoritmo de inserção funciona da mesma maneira com que muitas pessoas ordenam cartas em um jogo de baralho como o pôquer. Características principais:….

exibir mais
APS 3 Semestre
5718 palavras | 23 páginas

..07 3.1- ALGUNS METODOS UTILIZADOS NA ATUALIDADE.................09 4.0 MÉTODOS ULTILIZADO NA CONSTRUÇÃO DO SISTEMA.....................11 4.1 BUBBLE SORT…............................................................................11 4.2 QUICK SORT..................................................................................12 4.3 MERGE SORT................................................................................14 5.0- DOCUMENTAÇÃO BASE DO SISTEMA....................................….

exibir mais
apostila 2014
3055 palavras | 13 páginas

.............................................................................. 9 1.4. Implementação de Filas - Alocação Sequencial – em C ................................................................................................ 11 1.5. Exercícios ................................................................................................................................................................... 14 2- Métodos Simples de Ordenação de Vetores (Sorting) .......................….

exibir mais
Teste
2314 palavras | 10 páginas

Entre os mais importantes, podemos citar bubble sort (ou ordenação por flutuação), heap sort (ou ordenação por heap), insertion sort (ou ordenação por inserção), merge sort (ou ordenação por mistura) e o quicksort. Existem diversos outros, que o aluno pode com dedicação pesquisar por si. Para estudo, no entanto nos concentraremos nos principais:SelectionSort, Bubble Sort e Quicksort. Neste projeto utilizaremos os métodos: Selection Sort,Bubble Sort e Quicksort. O Método Pente (CombSort) Um ganho….

exibir mais
apostila c++/c UFU
1970 palavras | 8 páginas

Retângulo . . . . . . 1.3.3 Tipos Primitivos da Linguagem C 1.3.4 Organização do Código . . . . . . 1.4 Saída de Dados . . . . . . . . . . . . . . 1.5 A Função main . . . . . . . . . . . . . . 1.6 Conclusão . . . . . . . . . . . . . . . . . 1.7 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .….

exibir mais

Outros Trabalhos Populares