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/08/23
004//
005// Compara os 6 metodos de ordenacao abaixo, listando tempos de execucao:
006//  *  0 : O(n^2)     : Metodo da Bolha
007//  *  1 : O(n^2)     : Metodo da Selecao Direta
008//  *  2 : O(n^2)     : Metodo da Insercao Direta
009//  *  3 : O(n log n) : Metodo Rapido ("Quick Sort")
010//  *  4 : O(n log n) : Metodo da Fusao ("Merge Sort")
011//  *  5 : O(n log n) : Metodo do Monte ("Heap Sort")
012
013#include <stdio.h>
014#include <time.h> // clock_t, clock()
015
016#include "ordena_bolha.h"    // XbibliotecaLOBx__ordenaBolha(V, tam);
017#include "ordena_insercao.h" // XbibliotecaLOBx__ordenaViaInsercaoDireta(V, tam);
018#include "ordena_selecao.h"  // XbibliotecaLOBx__ordenaViaSelecaoDireta(V, tam);
019#include "ordena_rapido.h"   // XbibliotecaLOBx__ordenaRapido(int V[], int esq, int dir)
020#include "ordena_fusao.h"    // XbibliotecaLOBx__ordenaMetadesFusao(int V[], int esq, int dir)
021#include "ordena_monte.h"    // XbibliotecaLOBx__ordenaMonte(int V[], int tam)
022
023#define TAMINI    10000 // testar com TAMINI elementos inicialmente
024#define PASSO      1000 // crescimento no numero de elementos
025#define NTESTES      15 // numero de testes, de 1000 em 1000
026#define MAX       25000 // maximo de elementos (TAMINI + NTESTES * PASSO) - cuidado tambem usado no "ordena_fusao.h"
027#define INTERVALO  1000
028
029#define NMETODOS      6 // numero de metodos a serem testados
030
031// Gera 'n' valores pseudo-aleatorios para o vetor V[]
032void GeraVetor (int V[], int n) {
033  int i;
034  for (i=0; i<n; i++)
035    V[i] = (int)(rand()%INTERVALO); // rand() E {0,...,(2^31)-1  }, srand
036  }
037
038// Copia dados de vetor original
039void CopiaVetor (int VOrig[], int VNovo[], int n) {
040  int i;
041  for (i=0; i<n; i++) VNovo[i] = VOrig[i];
042  }
043
044// ImprimeVetor dados do vetor 
045void ImprimeVetor (int V[], int n) {
046  int i;
047  for (i=0; i<n; i++) printf("%4d", V[i]);
048  printf("\n");
049  }
050
051// Compara metodos de ordenacao
052int main (void) {
053  int V[MAX], V0[MAX];
054  int i, tam;
055  int TM[NMETODOS], md;
056  clock_t tempo_inicialB, tempo_finalB;
057  clock_t tempo_inicialSD, tempo_finalSD;
058  clock_t tempo_inicialID, tempo_finalID;
059  clock_t tempo_inicialR, tempo_finalR;
060  clock_t tempo_inicialF, tempo_finalF;
061  clock_t tempo_inicialM, tempo_finalM;
062
063  for (i=0; i<NMETODOS; i++) TM[i] = 0;
064
065  printf("      n |     Bolha | Sel. Dir. | Ins. Dir. | Met. Rap. | Met. Fus. | Met. Mon. |\n");
066
067  tam = TAMINI;
068  for (i=0; i<NTESTES; i++) {
069    GeraVetor(V0, tam);
070    //d ImprimeVetor(V0, tam); //d
071
072    // 0 : Metodo da Bolha
073    CopiaVetor(V0, V, tam);
074    tempo_inicialB = clock(); // "dispara o cronometro"...
075    XbibliotecaLOBx__ordenaBolha(V, tam);
076    tempo_finalB = clock();
077    TM[0] += tempo_finalB - tempo_inicialB;
078
079    // 1 : Metodo da Selecao Direta
080    CopiaVetor(V0, V, tam);
081    tempo_inicialSD = clock(); // "dispara o cronometro"...
082    XbibliotecaLOBx__ordenaViaSelecaoDireta(V, tam);
083    tempo_finalSD = clock();
084    TM[1] += tempo_finalSD - tempo_inicialSD;
085
086    // 2 : Metodo da Insercao Direta
087    CopiaVetor(V0, V, tam);
088    tempo_inicialID = clock(); // "dispara o cronometro"...
089    XbibliotecaLOBx__ordenaViaInsercaoDireta(V, tam);
090    tempo_finalID = clock();
091    TM[2] += tempo_finalID - tempo_inicialID;
092
093    // 3 : Metodo Rapido ("Quick Sort")
094    CopiaVetor(V0, V, tam);
095    tempo_inicialR = clock(); // "dispara o cronometro"...
096    XbibliotecaLOBx__ordenaRapido(V, 0, tam-1);
097    tempo_finalR = clock();
098    TM[3] += tempo_finalR - tempo_inicialR;
099
100    // 4 : Metodo da Fusao ("Merge Sort")
101    CopiaVetor(V0, V, tam);
102    tempo_inicialF = clock(); // "dispara o cronometro"...
103    XbibliotecaLOBx__ordenaMetadesFusao(V, 0, tam-1);
104    tempo_finalF = clock();
105    TM[4] += tempo_finalF - tempo_inicialF;
106
107    // 5 : Metodo do Monte ("Heap Sort")
108    CopiaVetor(V0, V, tam);
109    tempo_inicialM = clock(); // "dispara o cronometro"...
110    XbibliotecaLOBx__ordenaMonte(V, tam);
111    tempo_finalM = clock();
112    TM[5] += tempo_finalM - tempo_inicialM;
113    printf("  %5d |  %f |  %f |  %f |  %f |  %f |  %f |\n", tam,
114           (double)(tempo_finalB  - tempo_inicialB)  / CLOCKS_PER_SEC,
115           (double)(tempo_finalSD - tempo_inicialSD) / CLOCKS_PER_SEC,
116           (double)(tempo_finalID - tempo_inicialID) / CLOCKS_PER_SEC,
117           (double)(tempo_finalR  - tempo_inicialR)  / CLOCKS_PER_SEC,
118           (double)(tempo_finalF  - tempo_inicialF)  / CLOCKS_PER_SEC,
119           (double)(tempo_finalM  - tempo_inicialM)  / CLOCKS_PER_SEC);
120    tam += PASSO;
121    }
122
123  printf("    med |  %f |  %f |  %f |  %f |  %f |  %f |\n",
124         (double)(TM[0]) / (NTESTES * CLOCKS_PER_SEC), (double)(TM[1]) / (NTESTES * CLOCKS_PER_SEC),
125         (double)(TM[2]) / (NTESTES * CLOCKS_PER_SEC), (double)(TM[3]) / (NTESTES * CLOCKS_PER_SEC),
126         (double)(TM[4]) / (NTESTES * CLOCKS_PER_SEC), (double)(TM[5]) / (NTESTES * CLOCKS_PER_SEC));
127
128  printf("\n");
129
130  //d printf("\n\n\nDados iniciais:\n"); ImprimeVetor(V0, tam);
131  //d printf("\nOrdenado:\n"); ImprimeVetor(V, tam);
132
133  return 0;
134  }