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// MAC122
003// 2017/09/07
004//
005// Baseado no metodo de ordenacao para caracteres do tipo "digito menos significativo" ("least significant digits first" - LSD)
006// Exemplo de metodo no paradigma "GULOSO"
007// 
008// Aplicacao ao caso de inteiros: ordena supondo que numeros estao em pequena faixa de valores ("universo")
009// 
010// Usa a ideia de "vetor de bits" para representar conjunto: x presente <=> vet[x]==1.
011// Aqui usaremos o indice deslocado de 1                   : x presente <=> vet[x+1]==1
012// 
013// Complexidade do algoritmo de ordenacao : O(n + u), se u = #universo
014
015// Algumas referencias:
016// - "Chapter Ten. Radix Sorting" do livro do Sedgewick "Algorithms in C"/"C++ Programming"
017// - "Ordenacao digital", material do prof. Paulo Feofiloff: https://www.ime.usp.br/~pf/algoritmos/aulas/radix.html
018
019#include <stdio.h>  // para 'printf' e 'scanf'
020#include <stdlib.h> // para "rand()" para gerar valores "pseudo-aleatorios" (agilizar "entrada de dados")
021
022#define TAM        10 // tamanho para o vetor de dados (maximo de elementos no vetor de dados)
023#define INTERVALO 100 // gerar elementos entre 0..INTERVALO-1 para compor o conjunto "universo"
024
025// Prototipos para funcoes utilizadas (importante caso ocorra dependencia cruzada - funcao 'a()' depende de 'b()' e 'b()' depende de 'a()')
026void gerarVetorDados(int [], int, int);
027void imprimeVetor(int [], int);
028void ordenaPorFrequencia(int *, int, int); 
029
030// Gerar 'n' valores pseudo-aleatorios para o vetor V[]
031void gerarVetorDados (int V[], int n, int intervalo) {
032  int i;
033  for (i=0; i<n; i++)
034    V[i] = (int)(rand() % intervalo); //1 rand() gera inteiro entre {0,...,(2^31)-1  }, srand() pode mudar "semente"
035    //2 V[i] = n-i-1; //2 outro teste...
036    //3 V[i] = i % 2; //3 outro teste...
037  }
038
039// Imprime dados do vetor 
040void imprimeVetor (int V[], int n) {
041  int i;
042  for (i=0; i<n; i++)
043    printf("%4d", V[i]);
044  printf("\n");
045  }
046
047// Ordena crescente v[0..n-1] supondo que os elementos do vetor pertencem ao universo 0..U-1
048void ordenaPorFrequencia (int *vet, int n, int U) {
049  int ind, ii, i;
050  int *vetFreqAcum, *vetAux;
051  vetFreqAcum = malloc((U+1) * sizeof(int)); // para freq de cada diferente elemento
052  vetAux = malloc(n * sizeof(int)); // auxiliar para vetor de dados
053
054  // Ideia:
055  // 1. Computar frequencia de cada elemento considerando o "universo" (ideia de "vetor de bits"): O(n)
056  // 2. Acumular as frequencias (de 0 ate U-1) somando frequencia acumulada anterior (FAA)
057  // 3. A posicao da primeira ocorrencia de cada elemento e' dada pela FAA
058  //    A posicao da proxima ocorrencia do mesmo elemento e' na posicao seguinte
059
060  // 1. Computar frequencia de cada elemento considerando o "universo" (ideia de "vetor de bits"): O(n)  
061  for (i = 0; i <= U; i++) 
062    vetFreqAcum[i] = 0;
063  for (i = 0; i < n; ++i) { // anotar a freq de i na posicao i+1 => permite pegar a freq do 0 (0+1-1)
064    ind = vet[i]; // encontra posicao (ind) do elemento no "vetor de bits"
065    vetFreqAcum[ind+1]++; // mais uma ocorrencia desse elemento => usar posicao seguinte
066    //D1 printf(" %3d", vetFreqAcum[ind+1]); //D1 para examinar as frequencias
067    }
068  //D1 printf("\n");
069
070  // 2. Acumular as frequencias (de 0 ate U-1) somando frequencia acumulada anterior (FAA)
071  // Acumular frequencias: vetFreqAcum[i] recebera a frequencia de i-1 => recebe soma dos anteriores
072  for (i = 1; i <= U; i++) {
073    vetFreqAcum[i] += vetFreqAcum[i-1];
074    }
075  //D1 printf("FAA: "); imprimeVetor(vetFreqAcum, U); // no conj universo
076
077  // 3. A posicao da primeira ocorrencia de cada elemento e' dada pela FAA
078  //    A posicao da proxima ocorrencia do mesmo elemento e' na posicao seguinte
079  // Como vetFreqAcum[i] e' a freq. de todos os predecessores de i
080  // entao o elemento de i deve ser posicionado no indice vetFreqAcum[i] e proximas ocorrencias nas seguintes
081  for (i = 0; i < n; i++) {
082    ind = vet[i];                      // pegar indice do elemento no vetor "universo" (1 a menos pois o primeiro deve ir para 0 e sua freq e' 1)
083    vetAux[vetFreqAcum[ind]] = vet[i]; // colocar na posicao considerando os anteriores
084    vetFreqAcum[ind]++;                // a proxima ocorrencia do elemento i deve ir para proxima posicao
085    //D2 printf("(%2d) %2d para posicao %2d\n", ind-1, vet[i], vetFreqAcum[ind-1]);     
086    }
087  //D1 printf("FAA: "); imprimeVetor(vetFreqAcum, U);
088
089  // vetAux[0..n-1] este em ordem crescente
090  for (i = 0; i < n; ++i) 
091    vet[i] = vetAux[i];
092
093  free(vetFreqAcum); // libera memoria
094  free(vetAux);
095  }
096
097// inicia aqui...
098int main (void) {
099  int V[TAM], tam;
100  int continua, loc, x;
101  char c;
102
103  printf("\n\n\nDados iniciais:\n");   
104  tam = TAM;
105  gerarVetorDados(V, tam, INTERVALO);
106  imprimeVetor(V, tam);
107
108  ordenaPorFrequencia(V, tam, INTERVALO);
109
110  printf("\nOrdenado:\n");
111  imprimeVetor(V, tam);
112
113  return 0;
114  }