API tools faq
paste
Advertisement
techno-

P1 final no pienso hacer nada más

techno-
Oct 21st, 2022
61
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 8.87 KB | None | 0 0
raw download clone embed print report
  1. #include <stdio.h>
  2. #include <time.h>
  3. #include <stdlib.h>
  4. #include <sys/time.h>
  5. #include <math.h>
  6. #define UMBRAL 10
  7.  
  8. double microsegundos() {
  9.     struct timeval t;
  10.     if (gettimeofday(&t, NULL) < 0 )
  11.         return 0.0;
  12.     return (t.tv_usec + t.tv_sec * 1000000.0);
  13. }
  14.  
  15.  
  16. void ordenacionPorInsercion (int v[],int n) {
  17.     int i;
  18.     int j;
  19.     int x;
  20.  
  21.     for (i = 1; i <= n - 1; i++) {
  22.         x = v[i];
  23.         j = i - 1;
  24.         while (j > -1 && v[j] > x) {
  25.             v[j + 1] = v[j];
  26.             j = j - 1;
  27.         }
  28.         v[j + 1] = x;
  29.     }
  30. }
  31. void inicializar_semilla() {
  32.     srand(time(NULL));
  33. }
  34. void aleatorio(int v [], int n) {/* se generan números pseudoaleatorio entre -n y +n */
  35.     int i, m=2*n+1;
  36.     for (i=0; i < n; i++)
  37.         v[i] = (rand() % m) - n;
  38. }
  39. void ascendente(int v [], int n) {
  40.     int i;
  41.     for (i=0; i < n; i++)
  42.         v[i] = i;
  43. }
  44. void descendente(int v [], int n){
  45.     int i;
  46.     int j;
  47.     for (i=0; i < n; i++) {
  48.         j = 10 - i;
  49.         v[i] = j;
  50.     }
  51. }
  52.  
  53.  
  54.  
  55. void ordenarAux (int V[], int izq, int der) {
  56.     int i;
  57.     int j;
  58.     int x;
  59.     int Aux;
  60.     int pivote;
  61.     if (izq + UMBRAL <= der) {
  62.         x = (rand() % (der - izq + 1)) + izq;
  63.         pivote=V[x];
  64.         Aux=V[izq]; V[izq]=V[x]; V[x]=Aux;
  65.         i=izq +1;
  66.         j= der;
  67.         while(i<=j){
  68.             while(i<= der && V[i] < pivote){
  69.                 i=i+1;
  70.             }
  71.             while(V[j]>pivote){
  72.                 j=j-1;
  73.             }
  74.  
  75.             if(i<=j){
  76.                 Aux=V[i];V[i]=V[j];V[j]=Aux;
  77.                 i=i+1;
  78.                 j=j-1;
  79.             }
  80.         }
  81.         Aux=V[izq];V[izq]=V[j];V[j]=Aux;
  82.         ordenarAux(V,izq,j-1);
  83.         ordenarAux(V,j+1,der);
  84.     }
  85. }
  86. void ord_rapida(int v [], int n) {
  87.     ordenarAux(v, 0, n-1);
  88.     if (UMBRAL > 1)
  89.         ordenacionPorInsercion(v, n);
  90. }
  91.  
  92.  
  93. void test(){
  94.     inicializar_semilla();
  95.     int tamano=20;
  96.     int a[tamano];
  97.     int i;
  98.  
  99.     printf("Ordenacion por insercion con inicializacion aleatoria\n");
  100.     aleatorio(a,tamano);
  101.     for(i=0;i<tamano;i++){
  102.         printf("%d ",a[i]);
  103.     }
  104.     printf("\n");
  105.     ordenacionPorInsercion(a,tamano);
  106.     for(i=0;i<tamano;i++){
  107.         printf("%d ",a[i]);
  108.     }
  109.     printf("\nOrdenacion por insercion con inicializacion descendiente\n");
  110.     descendente(a,tamano);
  111.     for(i=0;i<tamano;i++){
  112.         printf("%d ",a[i]);
  113.     }
  114.     printf("\n");
  115.     ordenacionPorInsercion(a,tamano);
  116.     for(i=0;i<tamano;i++){
  117.         printf("%d ",a[i]);
  118.     }
  119. }
  120.  
  121. void test2(){
  122.     inicializar_semilla();
  123.     int tamano=20;
  124.     int a[tamano];
  125.     int i;
  126.     printf("Ordenacion rapida con inicializacion aleatoria\n");
  127.     aleatorio(a,tamano);
  128.     for(i=0;i<tamano;i++){
  129.         printf("%d ",a[i]);
  130.     }
  131.     printf("\n");
  132.     ord_rapida(a,tamano);
  133.     for(i=0;i<tamano;i++){
  134.         printf("%d ",a[i]);
  135.     }
  136.  
  137.     printf("\nOrdenacion rapida con inicializacion descendiente\n");
  138.     descendente(a,tamano);
  139.     for(i=0;i<tamano;i++){
  140.         printf("%d ",a[i]);
  141.     }
  142.     printf("\n");
  143.     ord_rapida(a,tamano);
  144.     for(i=0;i<tamano;i++){
  145.         printf("%d ",a[i]);
  146.     }
  147. }
  148.  
  149.  
  150.  
  151.  
  152. int main() {
  153.     printf("INSERCION\n");
  154.     test();
  155.     printf("\n");
  156.  
  157.     int k;
  158.     double ta,tb, t1, t2, t, x, y, z;
  159.     int n;
  160.  
  161.     printf("DESCENDENTE\n");
  162.     printf("           n           t(n)      t(n)/n^1.8      t(n)/n^2     t(n)/n^2.2\n");
  163.     for(n=500;n<=32000;n=n*2){
  164.         int a[n];
  165.         descendente(a,n);
  166.         ta=microsegundos();
  167.         ordenacionPorInsercion(a,n);
  168.         tb=microsegundos();
  169.  
  170.         t=tb-ta;
  171.         if(t<500){
  172.             ta=microsegundos();
  173.             for(k=0;k<1000;k++){
  174.                 descendente(a,n);
  175.                 ordenacionPorInsercion(a,n);
  176.             }
  177.             tb=microsegundos();
  178.             t1=tb-ta;
  179.  
  180.             ta=microsegundos();
  181.             for(k=0;k<1000;k++){
  182.                 descendente(a,n);
  183.             }
  184.             tb=microsegundos();
  185.             t2=tb-ta;
  186.             t=(t1-t2)/k;
  187.         }
  188.  
  189.         x = t / pow(n,1.8);
  190.         y = t / pow(n,2);
  191.         z = t / pow(n, 2.2);
  192.         printf("%12d%15.3f%15.6f%15.6f%15.6f\n", n, t, x, y, z);
  193.  
  194.     }
  195.  
  196.  
  197.     printf("\n");
  198.     printf("ASCENDENTE\n");
  199.  
  200.     printf("           n           t(n)      t(n)/n^1.8      t(n)/n^2     t(n)/n^2.2\n");
  201.     for(n=500;n<=32000;n=n*2){
  202.         int a[n];
  203.         ascendente(a,n);
  204.         ta=microsegundos();
  205.         ordenacionPorInsercion(a,n);
  206.         tb=microsegundos();
  207.  
  208.         t=tb-ta;
  209.         if(t<500){
  210.             ta=microsegundos();
  211.             for(k=0;k<1000;k++){
  212.                 ascendente(a,n);
  213.                 ordenacionPorInsercion(a,n);
  214.             }
  215.             tb=microsegundos();
  216.             t1=tb-ta;
  217.  
  218.             ta=microsegundos();
  219.             for(k=0;k<1000;k++){
  220.                 ascendente(a,n);
  221.             }
  222.             tb=microsegundos();
  223.             t2=tb-ta;
  224.             t=(t1-t2)/k;
  225.         }
  226.  
  227.         x = t / pow(n,1.8);
  228.         y = t / pow(n,2);
  229.         z = t / pow(n, 2.2);
  230.         printf("%12d%15.3f%15.6f%15.6f%15.6f\n", n, t, x, y, z);
  231.  
  232.     }
  233.  
  234.     printf("\n");
  235.     printf("ALEATORIO\n");
  236.  
  237.     printf("           n           t(n)      t(n)/n^1.8      t(n)/n^2     t(n)/n^2.2\n");
  238.     for(n=500;n<=32000;n=n*2){
  239.         int a[n];
  240.         aleatorio(a,n);
  241.         ta=microsegundos();
  242.         ordenacionPorInsercion(a,n);
  243.         tb=microsegundos();
  244.  
  245.         t=tb-ta;
  246.         if(t<500){
  247.             ta=microsegundos();
  248.             for(k=0;k<1000;k++){
  249.                 aleatorio(a,n);
  250.                 ordenacionPorInsercion(a,n);
  251.             }
  252.             tb=microsegundos();
  253.             t1=tb-ta;
  254.  
  255.             ta=microsegundos();
  256.             for(k=0;k<1000;k++){
  257.                 aleatorio(a,n);
  258.             }
  259.             tb=microsegundos();
  260.             t2=tb-ta;
  261.             t=(t1-t2)/k;
  262.         }
  263.  
  264.         x = t / pow(n,1.8);
  265.         y = t / pow(n,2);
  266.         z = t / pow(n, 2.2);
  267.         printf("%12d%15.3f%15.6f%15.6f%15.6f\n", n, t, x, y, z);
  268.  
  269.     }
  270.  
  271.  
  272.     printf("\n");
  273.     printf("RAPIDA\n");
  274.     test2();
  275.     printf("\n");
  276.     printf("DESCENDENTE\n");
  277.     printf("           n           t(n)      t(n)/n^0.8        t(n)/n^1.11      t(n)/n^1.5\n");
  278.     for(n=500;n<=32000;n=n*2){
  279.         int a[n];
  280.         descendente(a,n);
  281.         ta=microsegundos();
  282.         ord_rapida(a,n);
  283.         tb=microsegundos();
  284.  
  285.         t=tb-ta;
  286.         if(t<500){
  287.             ta=microsegundos();
  288.             for(k=0;k<1000;k++){
  289.                 descendente(a,n);
  290.                 ord_rapida(a,n);
  291.             }
  292.             tb=microsegundos();
  293.             t1=tb-ta;
  294.  
  295.             ta=microsegundos();
  296.             for(k=0;k<1000;k++){
  297.                 descendente(a,n);
  298.             }
  299.             tb=microsegundos();
  300.             t2=tb-ta;
  301.             t=(t1-t2)/k;
  302.         }
  303.  
  304.         x = t / pow(n,0.8);
  305.         y = t / pow(n,1.11);
  306.         z = t / pow(n, 1.5);
  307.         printf("%12d%15.3f%15.6f%15.6f%15.6f\n", n, t, x, y, z);
  308.  
  309.     }
  310.  
  311.     printf("\n");
  312.     printf("ASCENDENTE\n");
  313.     printf("           n           t(n)      t(n)/n^0.8        t(n)/n^1.11      t(n)/n^1.5\n");
  314.     for(n=500;n<=32000;n=n*2){
  315.         int a[n];
  316.         ascendente(a,n);
  317.         ta=microsegundos();
  318.         ord_rapida(a,n);
  319.         tb=microsegundos();
  320.  
  321.         t=tb-ta;
  322.         if(t<500){
  323.             ta=microsegundos();
  324.             for(k=0;k<1000;k++){
  325.                 ascendente(a,n);
  326.                 ord_rapida(a,n);
  327.             }
  328.             tb=microsegundos();
  329.             t1=tb-ta;
  330.  
  331.             ta=microsegundos();
  332.             for(k=0;k<1000;k++){
  333.                 ascendente(a,n);
  334.             }
  335.             tb=microsegundos();
  336.             t2=tb-ta;
  337.             t=(t1-t2)/k;
  338.         }
  339.  
  340.         x = t / pow(n,0.8);
  341.         y = t / pow(n,1.11);
  342.         z = t / pow(n, 1.5);
  343.         printf("%12d%15.3f%15.6f%15.6f%15.6f\n", n, t, x, y, z);
  344.  
  345.     }
  346.  
  347.     printf("\n");
  348.     printf("ALEATORIO\n");
  349.     printf("           n           t(n)      t(n)/n^0.8        t(n)/n^1.11      t(n)/n^1.5\n");
  350.     for(n=500;n<=32000;n=n*2){
  351.         int a[n];
  352.         aleatorio(a,n);
  353.         ta=microsegundos();
  354.         ord_rapida(a,n);
  355.         tb=microsegundos();
  356.  
  357.         t=tb-ta;
  358.         if(t<500){
  359.             ta=microsegundos();
  360.             for(k=0;k<1000;k++){
  361.                 aleatorio(a,n);
  362.                 ord_rapida(a,n);
  363.             }
  364.             tb=microsegundos();
  365.             t1=tb-ta;
  366.  
  367.             ta=microsegundos();
  368.             for(k=0;k<1000;k++){
  369.                 aleatorio(a,n);
  370.             }
  371.             tb=microsegundos();
  372.             t2=tb-ta;
  373.             t=(t1-t2)/k;
  374.         }
  375.  
  376.         x = t / pow(n,0.8);
  377.         y = t / pow(n,1.11);
  378.         z = t / pow(n, 1.5);
  379.         printf("%12d%15.3f%15.6f%15.6f%15.6f\n", n, t, x, y, z);
  380.  
  381.     }
  382.  
  383.  
  384.     return 0;
  385. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!