TrabalhosGratuitos.com - Trabalhos, Monografias, Artigos, Exames, Resumos de livros, Dissertações
Pesquisar

Etapa 1 atps analise e complexidade

Por:   •  22/4/2015  •  Trabalho acadêmico  •  1.866 Palavras (8 Páginas)  •  332 Visualizações

Página 1 de 8

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

...

Baixar como (para membros premium)  txt (5 Kb)   pdf (57.3 Kb)   docx (13.2 Kb)  
Continuar por mais 7 páginas »
Disponível apenas no TrabalhosGratuitos.com