API tools faq
paste
Advertisement
techno-

p2.c

techno-
Jan 15th, 2023
99
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 9.28 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.     int tamano=20;
  123.     int a[tamano];
  124.     int i;
  125.     inicializar_semilla();
  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. void insercionDESC(){
  150.     int k,n;
  151.     double ta,tb, t1, t2, t, x, y, z;
  152.     int a[32000];
  153.     printf("DESCENDENTE\n           n           t(n)      t(n)/n^1.8      t(n)/n^2     t(n)/n^2.2\n");
  154.     for(n=500;n<=32000;n=n*2){
  155.         descendente(a,n);
  156.         ta=microsegundos();
  157.         ordenacionPorInsercion(a,n);
  158.         tb=microsegundos();
  159.         t=tb-ta;
  160.         if(t<500){
  161.             ta=microsegundos();
  162.             for(k=0;k<1000;k++){
  163.                 descendente(a,n);
  164.                 ordenacionPorInsercion(a,n);
  165.             }
  166.             tb=microsegundos();
  167.             t1=tb-ta;
  168.  
  169.             ta=microsegundos();
  170.             for(k=0;k<1000;k++){
  171.                 descendente(a,n);
  172.             }
  173.             tb=microsegundos();
  174.             t2=tb-ta;
  175.             t=(t1-t2)/k;
  176.         }
  177.         x = t / pow(n,1.8);
  178.         y = t / pow(n,2);
  179.         z = t / pow(n, 2.2);
  180.         printf("%12d%15.3f%15.6f%15.6f%15.6f\n", n, t, x, y, z);
  181.     }
  182.     printf("\n");
  183. }
  184.  
  185. void insercionASC(){
  186.     int k,n;
  187.     double ta,tb, t1, t2, t, x, y, z;
  188.     int a[32000];
  189.     printf("ASCENDENTE\n           n           t(n)      t(n)/n^1.8      t(n)/n^2     t(n)/n^2.2\n");
  190.     for(n=500;n<=32000;n=n*2){
  191.         ascendente(a,n);
  192.         ta=microsegundos();
  193.         ordenacionPorInsercion(a,n);
  194.         tb=microsegundos();
  195.         t=tb-ta;
  196.         if(t<500){
  197.             ta=microsegundos();
  198.             for(k=0;k<1000;k++){
  199.                 ascendente(a,n);
  200.                 ordenacionPorInsercion(a,n);
  201.             }
  202.             tb=microsegundos();
  203.             t1=tb-ta;
  204.             ta=microsegundos();
  205.             for(k=0;k<1000;k++){
  206.                 ascendente(a,n);
  207.             }
  208.             tb=microsegundos();
  209.             t2=tb-ta;
  210.             t=(t1-t2)/k;
  211.         }
  212.         x = t / pow(n,1.8);
  213.         y = t / pow(n,2);
  214.         z = t / pow(n, 2.2);
  215.         printf("%12d%15.3f%15.6f%15.6f%15.6f\n", n, t, x, y, z);
  216.     }
  217.     printf("\n");
  218. }
  219.  
  220. void insercionALE(){
  221.     int k,n;
  222.     double ta,tb, t1, t2, t, x, y, z;
  223.     int a[32000];
  224.     printf("ALEATORIO\n           n           t(n)      t(n)/n^1.8      t(n)/n^2     t(n)/n^2.2\n");
  225.     for(n=500;n<=32000;n=n*2){
  226.         aleatorio(a,n);
  227.         ta=microsegundos();
  228.         ordenacionPorInsercion(a,n);
  229.         tb=microsegundos();
  230.         t=tb-ta;
  231.         if(t<500){
  232.             ta=microsegundos();
  233.             for(k=0;k<1000;k++){
  234.                 aleatorio(a,n);
  235.                 ordenacionPorInsercion(a,n);
  236.             }
  237.             tb=microsegundos();
  238.             t1=tb-ta;
  239.             ta=microsegundos();
  240.             for(k=0;k<1000;k++){
  241.                 aleatorio(a,n);
  242.             }
  243.             tb=microsegundos();
  244.             t2=tb-ta;
  245.             t=(t1-t2)/k;
  246.         }
  247.         x = t / pow(n,1.8);
  248.         y = t / pow(n,2);
  249.         z = t / pow(n, 2.2);
  250.         printf("%12d%15.3f%15.6f%15.6f%15.6f\n", n, t, x, y, z);
  251.     }
  252.     printf("\n");
  253. }
  254.  
  255. void insercion(){
  256.     printf("INSERCION\n");
  257.     test();
  258.     printf("\n");
  259.     insercionDESC();
  260.     insercionASC();
  261.     insercionALE();
  262. }
  263.  
  264. void rapidaDESC(){
  265.     int k,n;
  266.     double ta,tb, t1, t2, t, x, y, z;
  267.     printf("DESCENDENTE\n           n           t(n)      t(n)/n^0.8        t(n)/n^1.1      t(n)/n^1.5\n");
  268.     int a[32000];
  269.     for(n=500;n<=32000;n=n*2){
  270.         descendente(a,n);
  271.         ta=microsegundos();
  272.         ord_rapida(a,n);
  273.         tb=microsegundos();
  274.         t=tb-ta;
  275.         if(t<500){
  276.             ta=microsegundos();
  277.             for(k=0;k<1000;k++){
  278.                 descendente(a,n);
  279.                 ord_rapida(a,n);
  280.             }
  281.             tb=microsegundos();
  282.             t1=tb-ta;
  283.             ta=microsegundos();
  284.             for(k=0;k<1000;k++){
  285.                 descendente(a,n);
  286.             }
  287.             tb=microsegundos();
  288.             t2=tb-ta;
  289.             t=(t1-t2)/k;
  290.         }
  291.         x = t / pow(n,0.8);
  292.         y = t / pow(n,1.1);
  293.         z = t / pow(n, 1.5);
  294.         printf("%12d%15.3f%15.6f%15.6f%15.6f\n", n, t, x, y, z);
  295.     }
  296.     printf("\n");
  297. }
  298.  
  299. void rapidaASC(){
  300.     int k,n;
  301.     double ta,tb, t1, t2, t, x, y, z;
  302.     int a[32000];
  303.     printf("ASCENDENTE\n           n           t(n)      t(n)/n^0.8        t(n)/n^1.1      t(n)/n^1.5\n");
  304.     for(n=500;n<=32000;n=n*2){
  305.         ascendente(a,n);
  306.         ta=microsegundos();
  307.         ord_rapida(a,n);
  308.         tb=microsegundos();
  309.         t=tb-ta;
  310.         if(t<500){
  311.             ta=microsegundos();
  312.             for(k=0;k<1000;k++){
  313.                 ascendente(a,n);
  314.                 ord_rapida(a,n);
  315.             }
  316.             tb=microsegundos();
  317.             t1=tb-ta;
  318.             ta=microsegundos();
  319.             for(k=0;k<1000;k++){
  320.                 ascendente(a,n);
  321.             }
  322.             tb=microsegundos();
  323.             t2=tb-ta;
  324.             t=(t1-t2)/k;
  325.         }
  326.         x = t / pow(n,0.8);
  327.         y = t / pow(n,1.1);
  328.         z = t / pow(n, 1.5);
  329.         printf("%12d%15.3f%15.6f%15.6f%15.6f\n", n, t, x, y, z);
  330.     }
  331.     printf("\n");
  332. }
  333.  
  334. void rapidaALE(){
  335.     int k,n;
  336.     double ta,tb, t1, t2, t, x, y, z;
  337.     int a[32000];
  338.     printf("ALEATORIO\n           n           t(n)      t(n)/n^0.8        t(n)/n^1.1      t(n)/n^1.5\n");
  339.     for(n=500;n<=32000;n=n*2){
  340.         aleatorio(a,n);
  341.         ta=microsegundos();
  342.         ord_rapida(a,n);
  343.         tb=microsegundos();
  344.         t=tb-ta;
  345.         if(t<500){
  346.             ta=microsegundos();
  347.             for(k=0;k<1000;k++){
  348.                 aleatorio(a,n);
  349.                 ord_rapida(a,n);
  350.             }
  351.             tb=microsegundos();
  352.             t1=tb-ta;
  353.             ta=microsegundos();
  354.             for(k=0;k<1000;k++){
  355.                 aleatorio(a,n);
  356.             }
  357.             tb=microsegundos();
  358.             t2=tb-ta;
  359.             t=(t1-t2)/k;
  360.         }
  361.         x = t / pow(n,0.8);
  362.         y = t / pow(n,1.1);
  363.         z = t / pow(n, 1.5);
  364.         printf("%12d%15.3f%15.6f%15.6f%15.6f\n", n, t, x, y, z);
  365.     }
  366. }
  367.  
  368. void rapida(){
  369.     printf("RAPIDA\n");
  370.     test2();
  371.     printf("\n");
  372.     rapidaDESC();
  373.     rapidaASC();
  374.     rapidaALE();
  375. }
  376.  
  377.  
  378. int main() {
  379.     insercion();
  380.     rapida();
  381.     return 0;
  382. }
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!