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 Selecao 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
011int determineIndiceDoMenor (int vet[], int ini, int n) {
012  int indice, menor, i;
013  indice = ini;
014  menor = vet[ini];
015  for (i=ini+1; i<n; i++) { // invariante: vet[indice] <= vet[j], j em { ini, ini+1, ini+2, ... i-2, i-1 }
016    if (menor>vet[i]) { // novo menor
017      menor = vet[i];
018      indice = i;
019      }
020    } // complexidade: O(n)
021  return indice; // indice do menor entre vet[ini .. n-1]
022  }
023
024// Ordena via Selecao Direta
025void ordenaViaSelecaoDireta (int vet[], int n) {
026  int ii, imin, aux;
027  for (ii = 0; ii < n-1; ii++) { // invariante: vet[0]<=vet[1]<=...<=vet[ii-1] <= vet[j], j em { ii, ii+1, ..., n-1 }
028    imin = determineIndiceDoMenor(vet, ii, n);
029    aux = vet[ii];
030    vet[ii] = vet[imin];
031    vet[imin] = aux;
032    }  
033  } // complexidade: O(n^2)
034
035int main () {
036  int dados[MAX]; 
037  int n, ii, ordem;
038  printf("\n\n\nDados iniciais:\n");
039  // scanf ("%d", &n); for (ii = 0; ii < n; ii++) scanf("%d", &dados[ii]);
040  n = 10;
041  for (ii=0; ii<n; ii++) {
042    dados[ii] = rand() % INTERVALO;
043    printf("%3d", dados[ii]);
044    }
045
046  ordenaViaSelecaoDireta(dados, n);
047
048  printf("\nVetor ordenado:\n");
049  for (ii = 0; ii < n; ii++)
050    printf("%3d", dados[ii]);
051
052  printf("\n");
053  return 0;
054  }