Etapa 1 atps analise e complexidade
Por: schultz01 • 22/4/2015 • Trabalho acadêmico • 1.866 Palavras (8 Páginas) • 374 Visualizações
Etapa 2
•Passo 1
Algoritmo de ordenação por seleção:
Vantagens:
A principal vantagem desse estilo de algoritmo é que ela é muito eficiente com uma lista de poucas entradas. Ele também pode fazer o ordenação local, ou seja, não irá precisar de uma lista temporária para fazer isso.
Desvantagens:
A desvantagem desse algoritmo é com listas grandes, pois como ele exige n2 passos para n elementos, isso faz com que seu desempenho em listas grandes não seja muito eficiente.
Algoritmo de ordenação por inserção:
Vantagens:
É um algoritmo simples, muito eficiente com listas pequenas e já pré-ordenadas, pois com poucos elementos seu crescimento é linear e como é um algoritmo de ordenação local requer pouco espaço.
Desvantagens:
Comparado com outros algoritmos de ordenação não tem um bom desempenho, também não é muito eficiente com listas grandes porque tem seu numero de comparações com crescimento quadrático.
•Passo 2 e Passo 4
Algoritmo de ordenação por seleção:
void selection(int num[], int tam){ | ----------
int i, j, min, aux; | 1
for (i = 0; i < (tam-1); i++) { | N-1
min = i; | N-1
for (j = (i+1); j < tam; j++) { | N2
if(num[j] < num[min]) { | N2
min = j; | N2-1
} | ----------
} | ----------
if (i != min) { | N
aux = num[i]; | N-1
num[i] = num[min]; | N-1
num[min] = aux; | N-1
} | ----------
} | ----------
} | ----------
No pior caso o algoritmo fará 3N2+6N-5, logo sua complexidade será quadrática: O(N2).
Algoritmo de ordenação por inserção:
void insertion(int numeros[], int tam){ | ----------
int i, j, eleito; | 1
for (i = 1; i < tam; i++){ | N
eleito = numeros[i]; | N
j = i - 1; | N
while ((j>=0) && (eleito < numeros[j])) { | N2
numeros[j+1] = numeros[j]; | N2
j--; | N2
} | ----------
numeros[j+1] = eleito; | N
} | ----------
} | ----------
No pior caso o algoritmo fará 3N2+4N+1, logo sua complexidade será quadrática: O(N2).
•Passo 3
Algoritmo de ordenação por seleção:
void selection(int num[], int tam){ //Faz a chamada da função
int i, j, min, aux; //cria as variáveis que serão usadas na função
for (i = 0; i < (tam-1); i++) { //laço de repetição indo até o penúltimo elemento da lista
...