Material didático para princípios de desenvolvimento de Algoritmos

LinhaCodigo
001// Prof. Leo^nidas - http://www.matematica.br http://line.ime.usp.br
002// MAC0122 - 2017/08/21
003
004// Ordena vetor de inteiros via metodo Insercao Direta. Complexidade: O(n^2)
005
006#include <stdio.h>
007
008#define MAX 60
009#define INTERVALO 100  // para gerar valores pseudo-aleatorios (modulo 100 => numeros entre 0 e 99)
010
011// Ordena via Insercao Direta
012void ordenaViaInsercaoDireta (int vet[], int n) {
013  int ii, jj, aux;
014  for (ii = 1; ii < n; ii++) { // invariante: vet[0]<=vet[1]<=...<=vet[ii-1]
015    aux = vet[ii];
016    jj = ii;
017    while (jj > 0 && vet[jj-1] > aux) { // invariante antes da comparacao: aux < vet[j], j em { jj+1, jj+2, ..., ii }
018      vet[jj] = vet[jj-1];
019      jj--;
020      }
021    vet[jj] = aux; //
022    }
023  } // complexidade: O(n^2)
024
025int main () {
026  int dados[MAX]; 
027  int n, ii, ordem;
028  printf("\n\n\nDados iniciais:\n");
029  // scanf ("%d", &n); for (ii = 0; ii < n; ii++) scanf("%d", &dados[ii]);
030  n = 10;
031  for (ii=0; ii<n; ii++) {
032    dados[ii] = rand() % INTERVALO;
033    printf("%3d", dados[ii]);
034    }
035
036  ordenaViaInsercaoDireta(dados, n);
037
038  printf("\nVetor ordenado:\n");
039  for (ii = 0; ii < n; ii++)
040    printf("%3d", dados[ii]);
041
042  printf("\n");
043  return 0;
044  }