SHARE
TWEET

Untitled

a guest Apr 26th, 2019 64 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2.  
  3.  
  4. #include <iostream>
  5. #include<stdio.h>
  6. #include <string.h>
  7. #include <time.h>
  8. #define total_repet  560
  9. #define classes  4
  10. #define arquivos  15
  11. #define metodos  7
  12. using namespace std;
  13. #include "MetodosAss2.h"
  14. #include "Metodos2.cpp"
  15.  
  16.  
  17. Resul resul[total_repet];
  18.  
  19. int Maior(int vet[], int tam){
  20.   int maior = -1;
  21.  
  22.   for(int i=0; i<tam; i++){
  23.     if(vet[i] > maior){
  24.       maior = vet[i];
  25.     }
  26.   }
  27.   return maior;
  28. }
  29.  
  30.  
  31. int main()
  32. {
  33.     FILE *arq;
  34.     FILE *pont_arq;
  35.     char nomeArq[20];
  36.     int numero[20] = {100,200,500,1000,2000,5000,7500,10000,15000,30000,50000,75000,100000,200000,500000,750000,1000000,1250000,1500000,2000000};
  37.     int tam = 0, lixo, aux, contador = 0 ;
  38.  
  39.     for(int k=0;k<classes;k++){
  40.         for(int j=0; j<arquivos; j++){
  41.                 if(k==0){
  42.                   snprintf (nomeArq, sizeof(nomeArq), "a%d.txt", numero[j]);
  43.                 }
  44.                 if(k==1){
  45.                    snprintf (nomeArq, sizeof(nomeArq), "d%d.txt", numero[j]);
  46.                 }
  47.                 if(k==2){
  48.                     snprintf (nomeArq, sizeof(nomeArq), "o%d.txt", numero[j]);
  49.                 }
  50.                 if(k==3){
  51.                     snprintf (nomeArq, sizeof(nomeArq), "po%d.txt", numero[j]);
  52.                 }
  53.                 printf("nome arq: %s \n", nomeArq);
  54.                 arq = fopen(nomeArq, "r");
  55.                 while(fscanf(arq,"%d", &lixo) != EOF){
  56.                     tam++;
  57.                 }
  58.                 rewind(arq);
  59.                 int vet[tam], i=0, vetauxiliar[tam];
  60.                 int comeco=0, fim = tam-1, maior=0;
  61.                 while (fscanf(arq,"%d", &aux) != EOF){
  62.                     vet[i] = aux;
  63.                     i++;
  64.                 }
  65.  
  66.                 for(int cont=0; cont<tam; cont++){
  67.                   vetauxiliar[cont] = vet[cont];
  68.                 }
  69.  
  70.                 for(int alg=0;alg<metodos;alg++){
  71.                     for(int cont=0; cont<tam; cont++){
  72.                        vet[cont] = vetauxiliar[cont];
  73.                     }
  74.  
  75.                     strcpy(resul[contador].Nome_arq, nomeArq);
  76.                     if(alg==0){
  77.                         bubble_sort(vet,tam,contador,resul);
  78.                         strcpy(resul[contador].metodo, "bubble_sort");
  79.                         pont_arq = fopen("C:\\Users\\Fernando-\\Dropbox\\Trabalhos\\PAA\\TrabalhoPAA\\bubbleResul.txt", "a");
  80.                         fprintf(pont_arq, "%s %lld %lld %f \n", resul[contador].Nome_arq, resul[contador].swaps, resul[contador].compara, resul[contador].tempo );
  81.                     }
  82.                     if(alg==1){
  83.                         Insertion_sort(vet,tam,contador,resul);
  84.                         strcpy(resul[contador].metodo, "Insertion_sort");
  85.                         pont_arq = fopen("C:\\Users\\Fernando-\\Dropbox\\Trabalhos\\PAA\\TrabalhoPAA\\InsertionResul.txt", "a");
  86.                         fprintf(pont_arq, "%s %lld %lld %f \n", resul[contador].Nome_arq, resul[contador].swaps, resul[contador].compara, resul[contador].tempo );
  87.                     }
  88.                     if(alg==2){
  89.                         Selection_sort(vet,tam,contador,resul);
  90.                         strcpy(resul[contador].metodo, "Selection_sort");
  91.                         pont_arq = fopen("C:\\Users\\Fernando-\\Dropbox\\Trabalhos\\PAA\\TrabalhoPAA\\SelectionResul.txt", "a");
  92.                         fprintf(pont_arq, "%s %lld %lld %f \n", resul[contador].Nome_arq, resul[contador].swaps, resul[contador].compara, resul[contador].tempo );
  93.                     }
  94.                     if(alg==3){
  95.                         Merge_sort(vet,tam,contador,resul,comeco);
  96.                         strcpy(resul[contador].metodo, "Merge_sort");
  97.                         pont_arq = fopen("C:\\Users\\Fernando-\\Dropbox\\Trabalhos\\PAA\\TrabalhoPAA\\MergeResul.txt", "a");
  98.                         fprintf(pont_arq, "%s %lld %lld %f \n", resul[contador].Nome_arq, resul[contador].swaps, resul[contador].compara, resul[contador].tempo );
  99.                     }
  100.                     if(alg==4){
  101.                         quicksort(vet,comeco,tam,resul,contador);
  102.                         strcpy(resul[contador].metodo, "Quick_sort");
  103.                         pont_arq = fopen("C:\\Users\\Fernando-\\Dropbox\\Trabalhos\\PAA\\TrabalhoPAA\\QuickResul.txt", "a");
  104.                         fprintf(pont_arq, "%s %lld %lld %f \n", resul[contador].Nome_arq, resul[contador].swaps, resul[contador].compara, resul[contador].tempo );
  105.                     }
  106.                     if(alg==5){
  107.                         maior = Maior(vet,tam);
  108.                         Counting_sort(vet,tam,contador,maior,resul);
  109.                         strcpy(resul[contador].metodo, "Countting_sort");
  110.                         pont_arq = fopen("C:\\Users\\Fernando-\\Dropbox\\Trabalhos\\PAA\\TrabalhoPAA\\CounttingResul.txt", "a");
  111.                         fprintf(pont_arq, "%s %lld %lld %f \n", resul[contador].Nome_arq, resul[contador].swaps, resul[contador].compara, resul[contador].tempo );
  112.                     }
  113.                     if(alg==6){
  114.                         printf("entrou\n");
  115.                         Bucket_sort(vet,tam,contador,resul);
  116.                         strcpy(resul[contador].metodo, "Bucket_sort");
  117.                         pont_arq = fopen("C:\\Users\\Fernando-\\Dropbox\\Trabalhos\\PAA\\TrabalhoPAA\\BucketResul.txt", "a");
  118.                         fprintf(pont_arq, "%s %lld %lld %f \n", resul[contador].Nome_arq, resul[contador].swaps, resul[contador].compara, resul[contador].tempo );
  119.                         printf("saiu\n");
  120.                     }
  121.                     //printf("resul[contador].metodo %s \t contador = %d \n", resul[contador].metodo, contador);
  122.                     contador++;
  123.             }
  124.             tam= 0;
  125.         }
  126.     }
  127.     fclose(arq);
  128.     fclose(pont_arq);
  129.  
  130.     return 0;
  131. }
  132.  
  133. /////////////////////////////////////////////////
  134. #include "MetodosAss2.h"
  135. #include <iostream>
  136. #include <time.h>
  137. #include <stdio.h>
  138. #include <stdlib.h>
  139. #include <algorithm>
  140. #include <vector>
  141. using namespace std;
  142.  
  143. void Selection_sort(int vetor[], int n, int contador,  Resul *x) {
  144.  
  145.     long long int k, swaps = 0 , compara=0, indiceMenor;
  146.     time_t t_ini , t_fim;
  147.     t_ini = time(NULL);
  148.     for (k = 0; k < n; ++k) {
  149.       indiceMenor = k;
  150.         for (long long int indiceSeguinte = k+1; indiceSeguinte < n; ++indiceSeguinte) {
  151.             compara++;
  152.             if (vetor[indiceSeguinte] < vetor[indiceMenor]) {
  153.                 indiceMenor = indiceSeguinte;
  154.             }
  155.         }
  156.         swaps++;
  157.         long long int aux = vetor[k];
  158.         vetor[k] = vetor[indiceMenor];
  159.         vetor[indiceMenor] = aux;
  160.     }
  161.     t_fim = time(NULL);
  162.     x[contador].tempo = difftime(t_ini,t_fim);
  163.     x[contador].swaps = swaps;
  164.     x[contador].compara = compara;
  165. }
  166.  
  167. void Quick_sort(int values[], int comeco, int fim, Resul *x,  int contador){
  168.     long long int i, j, pivo, aux;
  169.     long long int swaps = 0 , compara=0;
  170.  
  171.     i = comeco;
  172.     j = fim-1;
  173.     pivo = values[(comeco + fim) / 2];
  174.     while(i <= j){
  175.         while(values[i] < pivo && i < fim){
  176.             compara++;
  177.             i++;
  178.         }
  179.         while(values[j] > pivo && j > comeco){
  180.             compara++;
  181.             j--;
  182.         }
  183.         swaps++;
  184.         if(i <= j){
  185.             aux = values[i];
  186.             values[i] = values[j];
  187.             values[j] = aux;
  188.             i++;
  189.             j--;
  190.         }
  191.     }
  192.     if(j > comeco)
  193.         Quick_sort(values, comeco, j+1, x, contador);
  194.     if(i < fim)
  195.         Quick_sort(values, i, fim, x, contador);
  196.  
  197.     x[contador].compara = compara;
  198.     x[contador].swaps = swaps;
  199. }
  200.  
  201. void quicksort(int values[], int comeco, int fim, Resul *x, int contador)
  202. {
  203.     time_t t_ini , t_fim;
  204.     t_ini = time(NULL);
  205.     Quick_sort(values, comeco, fim, x, contador);
  206.     t_fim = time(NULL);
  207.     x[contador].tempo = difftime(t_ini,t_fim);
  208. }
  209.  
  210. int merge(int vetor[], int comeco, int meio, int fim) {
  211.  
  212.     long long int compara=0, indiceMenor;
  213.     time_t t_ini , t_fim;
  214.     long long int com1 = comeco, com2 = meio+1, comAux = 0, tam = fim-comeco+1;
  215.     long long int *vetAux;
  216.     vetAux = (long long int*)malloc(tam * sizeof(long long int));
  217.  
  218.     while(com1 <= meio && com2 <= fim){
  219.       compara++;
  220.       if(vetor[com1] < vetor[com2]) {
  221.         vetAux[comAux] = vetor[com1];
  222.         com1++;
  223.       } else {
  224.         vetAux[comAux] = vetor[com2];
  225.         com2++;
  226.       }
  227.       comAux++;
  228.     }
  229.  
  230.     while(com1 <= meio){  //Caso ainda haja elementos na primeira metade
  231.       vetAux[comAux] = vetor[com1];
  232.       comAux++;
  233.       com1++;
  234.     }
  235.  
  236.     while(com2 <= fim) {   //Caso ainda haja elementos na segunda metade
  237.       vetAux[comAux] = vetor[com2];
  238.       comAux++;
  239.       com2++;
  240.     }
  241.  
  242.     for(comAux = comeco; comAux <= fim; comAux++){    //Move os elementos de volta para o vetor original
  243.       vetor[comAux] = vetAux[comAux-comeco];
  244.     }
  245.     free(vetAux);
  246.     return compara;
  247. }
  248.  
  249. void Merge_sort(int vetor[], int fim, int contador,  Resul *x, int comeco){
  250.     long long int swaps=0 , compara=0;
  251.     time_t t_ini , t_fim;
  252.     t_ini = time(NULL);
  253.     if(comeco < fim){
  254.         int meio = (comeco + fim) / 2;
  255.         Merge_sort(vetor, meio, contador, x, comeco);
  256.         Merge_sort(vetor, fim, contador, x, meio+1);
  257.         compara = merge(vetor, comeco, meio, fim);
  258.     }
  259.     t_fim = time(NULL);
  260.     x[contador].tempo = difftime(t_ini,t_fim);
  261.     x[contador].swaps = swaps;
  262.     x[contador].compara = compara;
  263. }
  264.  
  265. void Insertion_sort(int vetor[], int n, int contador,  Resul *x) {
  266.  
  267.     long long int k, j, aux, swaps = 0 , compara=0, escolhido;
  268.     time_t t_ini , t_fim;
  269.     t_ini = time(NULL);
  270.     for (k = 1; k < n; k++){
  271.       escolhido = vetor[k];
  272.       j = k - 1;
  273.       while ((j >= 0) && (vetor[j] > escolhido)) {
  274.         compara++;
  275.         swaps++;
  276.         vetor[j+1] = vetor[j];
  277.         j--;
  278.       }
  279.       compara++;
  280.       swaps++;
  281.       vetor[j+1] = escolhido;
  282.     }
  283.     t_fim = time(NULL);
  284.     x[contador].tempo = difftime(t_ini,t_fim);
  285.     x[contador].swaps = swaps;
  286.     x[contador].compara = compara;
  287. }
  288.  
  289. void Counting_sort(int values[], int tam, int contador, int maior, Resul *x){
  290.  
  291.   long long int i, j;
  292.   long long int C[maior+1], B[tam];
  293.   long long int swaps = 0 , compara=0;
  294.   time_t t_ini , t_fim;
  295.  
  296.  
  297.   t_ini = time(NULL);
  298.  
  299.   for (i=0; i<=maior; i++)
  300.         C[i]=0;
  301.  
  302.   for (j=0; j<tam; j++)
  303.         C[values[j]] = C[values[j]] + 1;
  304.  
  305.   for (i=1; i<maior; i++)
  306.         C[i] = C[i] + C[i-1];
  307.  
  308.   for (j=tam-1; j>=0; j--){
  309.         B[C[values[j]]-1] = values[j];
  310.         C[values[j]] = C[values[j]]-1;
  311.   }
  312.   t_fim = time(NULL);
  313.   x[contador].tempo = difftime(t_ini,t_fim);
  314.   x[contador].swaps = swaps;
  315.   x[contador].compara = compara;
  316.  
  317. }
  318.  
  319. void bubble_sort(int vetor[], int n, int contador, Resul *x) {
  320.  
  321.     long int k, j, aux ;
  322.     long long int swaps = 0, compara=0;
  323.     float tempo = 0;
  324.     time_t t_ini , t_fim;
  325.     time(&t_ini);
  326.     for (k = 1; k < n; k++) {
  327.         for (j = 0; j < n - 1; j++) {
  328.             compara++;
  329.             if (vetor[j] > vetor[j + 1]) {
  330.                 swaps++;
  331.                 //printf("swap = %ld \n", swaps);
  332.                 aux = vetor[j];
  333.                 vetor[j] = vetor[j+1];
  334.                 vetor[j+1] = aux;
  335.             }
  336.         }
  337.     }
  338.     time(&t_fim);
  339.     float tempo_bub = difftime(t_fim, t_ini);
  340.  
  341.     x[contador].tempo = tempo_bub;
  342.     x[contador].swaps = swaps;
  343.     x[contador].compara = compara;
  344.  
  345. }
  346.  
  347.  
  348. struct bucket
  349. {
  350.     int count;
  351.     int* value;
  352. };
  353.  
  354. int compareIntegers(const void* first, const void* second)
  355. {
  356.     int x = *((int*)first), y =  *((int*)second);
  357.     if (x == y)
  358.     {
  359.         return 0;
  360.     }
  361.     else if (x < y)
  362.     {
  363.         return -1;
  364.     }
  365.     else
  366.     {
  367.         return 1;
  368.     }
  369. }
  370. void Bucket_sort(int array[], int n, int contador, Resul *x){
  371.  
  372.   time_t t_ini,t_fim;
  373.   long long int swaps=0, compara=0;
  374.  
  375.  
  376.     struct bucket buckets[3];
  377.     int i, j, k;
  378.     t_ini = time(NULL);
  379.     for (i = 0; i < 3; i++){
  380.         buckets[i].count = 0;
  381.         buckets[i].value = (int*)malloc(sizeof(int) * n);
  382.     }
  383.     for (i = 0; i < n; i++){
  384.         compara += 2;
  385.         if (array[i] < 0)
  386.         {
  387.             buckets[0].value[buckets[0].count++] = array[i];
  388.         }
  389.         else if (array[i] > 10){
  390.             buckets[2].value[buckets[2].count++] = array[i];
  391.         }
  392.         else
  393.         {
  394.             buckets[1].value[buckets[1].count++] = array[i];
  395.         }
  396.     }
  397.     for (k = 0, i = 0; i < 3; i++){
  398.         // now using quicksort to sort the elements of buckets
  399.         qsort(buckets[i].value, buckets[i].count, sizeof(int), &compareIntegers);
  400.         for (j = 0; j < buckets[i].count; j++){
  401.             array[k + j] = buckets[i].value[j];
  402.         }
  403.         k += buckets[i].count;
  404.         free(buckets[i].value);
  405.     }
  406.  
  407.  
  408.   t_fim = time(NULL);
  409.  
  410.   x[contador].tempo = difftime(t_ini,t_fim);
  411.   x[contador].swaps = swaps;
  412.   x[contador].compara = compara;
  413.  
  414. }
  415.  
  416.  
  417.  
  418. //////////////////////////////
  419. #ifndef METODOSASS
  420. #define METODOSASS
  421.  
  422. struct Resultados{
  423.  
  424.     char metodo[500];
  425.     char Nome_arq[500];
  426.     long long int swaps;
  427.     long long int compara;
  428.     float tempo;
  429. };
  430. typedef struct Resultados Resul;
  431.  
  432. void Bucket_sort(int values[], int tam, int contador,  Resul *x);
  433. void Counting_sort(int values[], int tam, int contador, int maior,  Resul *x);
  434. void Insertion_sort(int vetor[], int n, int contador,  Resul *x);
  435. void Merge_sort(int vetor[], int fim, int contador,  Resul *x, int comeco);
  436. void bubble_sort(int vetor[], int n, int contador,  Resul *x);
  437. void quicksort(int values[], int comeco, int fim,  Resul *x,  int contador);
  438. void Selection_sort(int vetor[], int n, int contador,  Resul *x);
  439.  
  440. #endif
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top