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// Compara tempo efetivo de execucao de 2 metods de ordenacao, SEM trocar efetivamente as "strings" de posicao,
006// usando vetor auxiliar para ordem (main.vetOrdem[]). Os metodos sao "Bolha" e "Radix".
007// Supoe que os nomes usam apenas caracteres de 'a' ate' 'z' (pequena faixa de valores para "universo")
008
009// Le arquivo com N+1 linhas, estando na primeir "N" e nas seguintes um nome cada
010
011// Complexidade Bolha: O(n*n * u), se u = comprimento medio das palavras
012// Complexidade Radix: O(n + u), se u = #universo
013
014// Exercicio 1: Altere o codigo para ler as linhas e deduzir numero nomes
015// Exercicio 2: Prove que o algoritmo de ordenacao Radiz e' de fato estavel
016
017// Para depurar gerenciamento de memoria em caso de erro de 'malloc/free':
018//  $ gcc -fsanitize=address -g -o ordena_string_por_frequencia ordena_string_por_frequencia.c
019// Para compilar com caracteres especiais "L'\u00e1"
020//  $ gcc -fsanitize=address -g -std=c99 -o ordena_string_compara_metodos ordena_string_compara_metodos.c
021
022// Arquivos para teste:
023// https://pt.wikipedia.org/wiki/Categoria:Matemáticos_do_Brasil
024
025// Referencias:
026// 1. "Chapter Ten. Radix Sorting" do Sedgewick (pg 154 "Program 10.2. MSD radix sort")
027// 2. Paulo Feofilof: https://www.ime.usp.br/~pf/algoritmos/
028
029#include <stdio.h>
030#include <stdlib.h> // para "rand()"
031#include <string.h> // para "strcmp(...)" e "strcpy(...)"
032#include <time.h>   // para "clock_t", "clock()"
033
034#define MAX           5000 // maximo de elementos
035#define TAM             10 // testar com TAM elementos
036#define MAXCOMPLINHA  1024 // tamanho maximo de uma linha
037#define INTERVALO       27 // 'A' ate 'Z' (97 a 122)
038
039
040// Comprimento de "strings"
041int comprimento (char *vetStr) { // evita "strlen(vetStr[i])" devolvendo 1 a mais...
042  int i = 0;
043  while (vetStr[i]!='\0' && vetStr[i]!='\n') i++;
044  return i;
045  }
046
047// Tentativa de trocar caracteres especiais para "base" em ASCII
048// Ver: https://www.w3.org/People/danield/unic/unitra.htm ; https://www.w3.org/International/questions/qa-what-is-encoding
049void sanitarizaASCII (int ind, char *nome) {
050  int i = 0;
051  char c1; //unsigned
052  wchar_t c; // para conseguir armazenar caractere "estendido" (2 bytes)
053  while ((c=nome[i])!='\0' && c!='\n') {
054    if (c==' ') {
055      }
056    else
057    if (c>='A' && c<='Z') { // 'A'=65, 'B'=66, ... 'W'=87, 'x'=88, 'y'=89, 'z'=90
058      nome[i] = c + ('a' - 'A');
059      }
060    else
061    if (c<'a' || c>'z') { // 'a'=97, 'b'=98, ... 'w'=119, 'x'=120, 'y'=121, 'z'=122
062      switch (c) { // tente trocar alguns caracteres usando notacao Unicode
063        case L'\u00e1' : // a'
064        case L'\u00e0' : // `a
065        case L'\u00e2' : // a^
066        case L'\u00e3' : // a~
067        case L'\u00e4' : // a"
068             c1 = 'a'; printf(" *** i=%d, %s", i, nome); break;
069        // ...
070        case L'\u00e7' : // c,
071             c1 = 'c'; printf(" *** i=%d, %s", i, nome); break;
072        default: c1 = ' ';
073        }
074      nome[i] = c1;
075      } //printf("2: nome=%s", nome);
076    i++;
077    }
078  }
079
080// Ler uma linha do arquivo apontado
081char * leituraElemento (FILE *aptf, int i, char linha[]) {
082  if (fgets(linha, MAXCOMPLINHA, aptf)==NULL || ferror(aptf) || feof(aptf) ) { // char *fgets(char *str, int n, FILE *stream)
083    if (comprimento(linha)>0) { // tratar caso de ultima linha ter nome
084      sanitarizaASCII(i, linha); // tenta "limpar" linha eliminando caracteres especiais (i apenas apoio 'a depuracao)
085      return linha;
086      }
087    return NULL; // final de arquivo
088    }
089  sanitarizaASCII(i, linha);
090  return linha;
091  }
092
093// Leia vetor de "string", devolva o comprimento da maior (uniformiza todas)
094int leituraVetor (FILE *apf, char vetStr[][MAXCOMPLINHA], int vetOrdem[], int *N) {
095  int *vetComprimentos;
096  int i = 0, j, tamI, max = -1; //, imax;
097  fscanf(apf, "%d", N);
098  if (*N > MAX) {
099    // printf("Erro! Primeira linha do arquivo de 'string' afirma existirem %d elementos, mas limite e' %d!\n", *N, MAX);
100    return -*N;
101    }
102  vetComprimentos = malloc(*N * sizeof(int)); // comprimento das palavras (evita computar 2 vezes)
103
104  leituraElemento(apf, 0, vetStr[0]); // pula restante da linha
105
106  for (i = 0; i < *N; i++) {
107    if (leituraElemento(apf, i, vetStr[i]) == NULL) { // EOF
108      i--;
109      break;
110      }
111    tamI = comprimento(vetStr[i]); // para nao usar "strlen(vetStr[i]" que pode devolver 1 a mais...     
112    vetComprimentos[i] = tamI;
113    //D printf("#=%d : vetStr[%d]=%s", tamI, i, vetStr[i]);
114    if (tamI>max) { max = tamI; } // imax = i; }
115    }
116
117  printf("leituraVetor: maior linha tem max=%d caracteres\n", max);
118  for (i = 0; i < *N; i++) { // para uniformizar
119    vetOrdem[i] = i; // ordem inicial e' identidade
120    for (j = vetComprimentos[i]; j < max; j++) { // uniformiza "strings"
121      vetStr[i][j] = ' ';
122      }
123    vetStr[i][j] = '\0';
124    }
125  free(vetComprimentos); // libera memoria alocada
126  return max;
127  } // int leituraVetor(FILE *apf, char vetStr[][MAXCOMPLINHA], int vetOrdem[], int *N)
128
129void iniciaVetorOrdem (int ord[], int N) {
130  int i;
131  for (i = 0; i < N; i++)
132    ord[i] = i;
133  }
134
135// Auxilia depuracao
136void imprimeVetorOrdem (int ord[], int N) {
137  int i;
138  for (i = 0; i < N; i++) {
139    printf("%3d", ord[i]);
140    }
141  printf("\n");
142  }
143
144// Imprime vetor de nomes usando vetor de ordem "ord[]"
145void imprimeVetor (FILE *ap, char vetStr[][MAXCOMPLINHA], int ord[], int N) {
146  int i;
147  for (i = 0; i < N; i++) {
148    fprintf(ap, " %3d : |%s|\n", i, vetStr[ord[i]]);
149    }
150  }
151
152void imprimeVetorDireto (char vetStr[][MAXCOMPLINHA], int N) {
153  int i;
154  for (i = 0; i < N; i++) {
155    printf(" %3d : |%s|\n", i, vetStr[i]);
156    }
157  }
158
159//--------------------------------------------------------------------------
160// Ordena via Bolha por vetor auxiliar (sem trocar elementos)
161void trocaEmVetorOrd (int vetOrdem[], int i, int j) {
162  int aux;
163  aux = vetOrdem[i];
164  vetOrdem[i] = vetOrdem[j];
165  vetOrdem[j] = aux;
166  }
167
168void ordenaBolhaOrdem (char vetStr[][MAXCOMPLINHA], int ord[], int N) {
169  int i, j;
170  for (i = 1; i <= N; i++) {
171    for (j = i; j > 0; j--) {
172      if (strcmp(vetStr[ord[j-1]], vetStr[ord[j]]) > 0)
173        trocaEmVetorOrd(ord, j, j-1);
174      }
175    }
176  }
177
178//--------------------------------------------------------------------------
179// Ordena via Bolha trocando elementos
180void trocaEmVetor (char vetStr[][MAXCOMPLINHA], int i, int j) {
181  char aux[MAXCOMPLINHA]; // como trata-se de "string", cada copia e' um laco
182  strcpy(aux, vetStr[i]);       // aux = vetStr[i];
183  strcpy(vetStr[i], vetStr[j]); // vetStr[i] = vetStr[j];
184  strcpy(vetStr[j], aux);       // vetStr[j] = aux;
185  }
186
187// Ordena via bolha trocando elementos
188void ordenaBolha (char vetStr[][MAXCOMPLINHA], int N) {
189  int i, j;
190  for (i = 1; i <= N; i++) {
191    for (j = i; j > 0; j--) {
192      if (strcmp(vetStr[j-1], vetStr[j]) > 0)
193        trocaEmVetor(vetStr, j, j-1);
194      }
195    }
196  }
197
198//--------------------------------------------------------------------------
199// Ideia de "vetor de bits" associando caracteres ' ', 'a', 'b', 'c', ... 'as posicoes 0, 1, 2, ... do vetor
200// Entretanto para funcionar o computo de frequencias acumuladas
201// Devolve como indice a posicao seguinte (para liberar o 0 e permitir pegar o anterior dele)
202int pegaIndice (char c, int U, int desc) {
203  int ind;                // indice do caractere: ' ' = 32 -> 1; 'a' -> 2; 'b' -> 3; ...
204  if (c==' ') ind = 1;    // encontra posicao (ind) do elemento no vetor auxiliar
205  else ind = c - 'a' + 2; // 'a' -> 2; 'b' -> 3; ...
206  if (ind<0 || ind>U) {   // detectar valores do "universo" erroneos...
207    printf("Erro: ultrapassou universo previso!\nCaractere '%c' = %d -> %d > %d\n", c, c, ind, U);
208    return -1;
209    }
210  return ind;
211  }
212
213// Ordena crescente v[0..n-1] supondo que os elementos do vetor pertencem ao universo 0..U-1
214// Utiliza vetor de ordem 'vetOrdem[]' para NAO mover "strings"
215// Supoe que vetor de "strings" 'vetStr[][]' esteja uniformizado
216// (todas de mesmo comprimento, completadas com brancos 'a direita)
217// IMPORTANTE: o metodo de ordenacao por "digito" menos significative e' estavel
218void ordenaPorFrequencia (char vetStr[][MAXCOMPLINHA], int vetOrdem[], int tamLnh, int n, int U) {
219  int ind, jj, i;
220  int *vetFreqAcum, *vetAux, *vetOrd1;
221  char *vet;
222  vetFreqAcum = malloc((U+1) * sizeof(int)); // para freq de cada diferente elemento
223  vetAux = malloc(n * sizeof(char)); // auxiliar para vetor de dados
224  vet = malloc(n * sizeof(char)); // auxiliar para armazenar caractere da posicao jj das "strings"
225  vetOrd1 = malloc(n * sizeof(int)); // auxiliar para atualizar vetor de ordem
226
227  // Ideia:
228  // 1. Computar frequencia de cada elemento considerando o "universo" (ideia de "vetor de bits"): O(n)
229  // 2. Acumular as frequencias (de 0 ate U-1) somando frequencia acumulada anterior (FAA)
230  // 3. A posicao da primeira ocorrencia de cada elemento eh dada pela FAA
231  //    A proxima ocorrencia do elemento eh na posicao seguinte
232
233  // Ordenar por "digito" menos significativo, como metodo e' estavel ao final ordena tudo
234  for (jj = tamLnh-1; jj >= 0; jj--) {
235
236    // 1. Computar frequencia de cada elemento considerando o "universo" (ideia de "vetor de bits"): O(n)  
237    for (i = 0; i <= U; i++) 
238      vetFreqAcum[i] = 0;
239    for (i = 0; i < n; ++i) {
240      vet[i] = vetStr[vetOrdem[i]][jj]; // pegar caractere respeitando a ordem
241      if (vet[i]=='\0' || vet[i]==0) { // detecta erro: caractere invalido
242        printf("Erro em ordenacao: caractere invalido na posicao %d de %s\n", jj, vetStr[i]); return;
243        }
244      ind = pegaIndice(vet[i], U, 0);
245      if (ind<0) { // detecta erro: caractere fora do "universo" previso
246        printf("Erro em ordenacao (1): indice invalido! (jj=%d, i=%d, c=%c)\n%s\n", jj, i, vet[i], vetStr[jj]); return;
247        }
248      vetFreqAcum[ind]++; // mais uma ocorrencia desse elemento
249      }
250
251    // 2. Acumular as frequencias (de 0 ate U-1) somando frequencia acumulada anterior FAA  
252    // Acumular frequencias: vetFreqAcum[i] recebera a frequencia de i-1 => recebe soma dos anteriores
253    for (i = 1; i <= U; i++) {
254      vetFreqAcum[i] += vetFreqAcum[i-1];
255      }
256
257    // 3. A posicao da primeira ocorrencia de cada elemento eh dada pela FAA
258    //    A proxima ocorrencia do elemento eh na posicao seguinte
259    // Como vetFreqAcum[i] eh a freq de todos os predecessores de i
260    // entao o elemento de i deve ser posicionado no indice vetFreqAcum[i] e proximas ocorrencias nas seguintes
261    for (i = 0; i < n; i++) {
262      ind =  pegaIndice(vet[i], U, 1) - 1; // pegar indice do elemento no vetor "universo" (1 a menos pois o primeiro deve ir para 0 e sua freq e' 1)
263      if (ind<0) { printf("Erro em ordenacao (2): indice invalido! (jj=%d, i=%d, c=%c)\n|%s|\n", jj, i, vet[i], vetStr[i]); return; }
264
265      // vetOrd1[0..n-1] fornece "strings" em ordem crescente (menor na posicao 'vetOrdem[0]'
266      vetOrd1[vetFreqAcum[ind]] = vetOrdem[i]; // elemento i tem posicao de ordem final 'vetFreqAcum[ind]'
267
268      vetFreqAcum[ind]++;  // a proxima ocorrencia do elemento i deve ir para proxima posicao
269      }
270
271    // vetOrdem[0..n-1] fornece "strings" em ordem crescente (menor na posicao 'vetOrdem[0]'
272    for (i = 0; i < n; i++) // nova ordem
273      vetOrdem[i] = vetOrd1[i]; 
274
275    } // for (jj = tamLnh-1; jj >= 0; jj--)
276
277  free(vetFreqAcum); // libera memorias alocadas - importante se este metodo ficar ativo
278  free(vetAux);
279  free(vet);
280
281  } // void ordenaPorFrequencia(char vetStr[][MAXCOMPLINHA], int vetOrdem[], int tamLnh, int n, int U)
282
283// inicia aqui...
284int main (int argc, char *argv[]) {
285  FILE *apontEntrada, *apontSaida;
286  char vetorDados[MAX][MAXCOMPLINHA];
287  int vetOrdem[MAX];
288  clock_t tempo_inicialF, tempo_finalF;   // via 'include "time.h"' para pegar tempo
289  clock_t tempo_inicialB1, tempo_finalB1;
290  clock_t tempo_inicialB2, tempo_finalB2;
291
292  int tam, max;
293
294  if (argc < 2) { //2 (argc < 3)
295    //2 printf("Erro: eram esperados 2 nomes de arquivos, primeiro com nomes para ordenacao, segundo para saidas\n");
296    //2 printf("./ordena_string_por_frequencia entradas saidas\n");
297    printf("Erro: era esperado o nomes do arquivo com nomes a serem ordenados (primeira linha com N, seguido de N nomes)\n");
298    printf("./ordena_string_compara_metodos entradas\n");
299    return 1;
300    }
301
302  printf("Abre %s\n", argv[1]);
303  apontEntrada = fopen(argv[1], "r");
304
305  max = leituraVetor(apontEntrada, vetorDados, vetOrdem, &tam); // pegue tamanho uniformizado das "strings"
306  fclose(apontEntrada);
307  if (max < 0) {
308    printf("Erro! Primeira linha do arquivo de 'string' afirma existirem %d elementos, mas limite e' %d!\n", -max, MAX);
309    return 1;
310    }
311  
312  printf("\n\n\nDados iniciais:\n");   
313  imprimeVetor(stdout, vetorDados, vetOrdem, tam);
314
315  // 1. Ordena via frequencia (Radix) SEM trocas nas posicoes das "strings"
316  tempo_inicialF = clock();
317  ordenaPorFrequencia(vetorDados, vetOrdem, max, tam, INTERVALO);
318  tempo_finalF = clock();
319
320  printf("\nOrdenado por Frequencia sem trocas:\n");
321  imprimeVetor(stdout, vetorDados, vetOrdem, tam);
322
323  //2 printf("Abre arquivo para registrar nomes ordenados: %s\n", argv[2]);
324  //2 apontSaida = fopen(argv[2], "w"); //
325  //2 imprimeVetor(apontSaida, vetorDados, vetOrdem, tam);
326  //2 fclose(apontSaida);
327
328  // 2. Ordena via Bolha SEM trocas nas posicoes das "strings"
329  iniciaVetorOrdem(vetOrdem, tam);
330  tempo_inicialB1 = clock();
331  ordenaBolhaOrdem(vetorDados, vetOrdem, tam-1);
332  tempo_finalB1 = clock();
333  printf("\nOrdenado por Bolha sem trocas:\n");
334  imprimeVetor(stdout, vetorDados, vetOrdem, tam);
335
336  // 3. Ordena via Bolha COM trocas nas posicoes das "strings"
337  tempo_inicialB2 = clock();
338  ordenaBolha(vetorDados, tam-1);
339  tempo_finalB2 = clock();
340  printf("\nOrdenado por Bolha com trocas:\n");
341  imprimeVetorDireto(vetorDados, tam);
342
343  printf(" tam = %5d\nTempos de execucao\n * Frequencia = %fs\n * Bolha ordem= %fs\n * Bolha      = %fs\n", tam,
344         (double)(tempo_finalF  - tempo_inicialF)  / CLOCKS_PER_SEC,
345         (double)(tempo_finalB1 - tempo_inicialB1) / CLOCKS_PER_SEC,
346         (double)(tempo_finalB2 - tempo_inicialB2) / CLOCKS_PER_SEC);
347
348  return 0;
349  }