API tools faq
paste
tomasfdel

Estructuras I Práctica 6

tomasfdel
Jul 20th, 2017
329
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 9.71 KB | None | 0 0
raw download clone embed print report
  1. ///EJERCICIOS 2-4
  2.  
  3.  
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6.  
  7. void swapp (int *a, int *b){
  8.     int aux = *a;
  9.     *a = *b;
  10.     *b = aux;
  11. }
  12.  
  13. void ssort(int array[], int largo){
  14.     int menor, posMenor;
  15.     for(int i = 0; i < largo; i++){
  16.         menor = array[i];
  17.         posMenor = i;
  18.         for(int j = i + 1; j < largo; j++){
  19.             if(array[j] < menor){
  20.                 menor = array[j];
  21.                 posMenor = j;
  22.             }
  23.         }
  24.         swapp(&array[i], &array[posMenor]);
  25.     }
  26. }
  27.  
  28. void isort(int array[], int largo){
  29.     for(int i = 0; i < largo; i++){
  30.         for(int j = i; j > 0; j--){
  31.             if(array[j] >= array[j-1])
  32.                 break;
  33.             else
  34.                 swapp(&array[j-1], &array[j]);
  35.         }
  36.     }
  37. }
  38.  
  39. void bsort(int array[], int largo){
  40.     int flag = 0;
  41.     for(int j = largo; j > 0; j--){
  42.         flag = 1;
  43.         for(int i = 0; i < j-1; i++){
  44.             if(array[i] > array[i+1]){
  45.                 swapp(&array[i], &array[i+1]);
  46.                 flag = 0;
  47.             }
  48.         }
  49.     if(flag) break;
  50.     }
  51. }
  52.  
  53. int main(){
  54.     int array[] = {0,14,-7,9,4,59,-20,1,2,3};
  55.     ssort(array, 10);
  56.     for(int i = 0; i < 10; i++)
  57.         printf("%d ", array[i]);
  58.     printf("\n");
  59.  
  60.  
  61.     int array2[] = {0,14,-7,9,4,59,-20,1,2,3};
  62.     isort(array2, 10);
  63.     for(int i = 0; i < 10; i++)
  64.         printf("%d ", array2[i]);
  65.     printf("\n");
  66.  
  67.  
  68.     int array3[] = {0,14,-7,9,4,59,-20,1,2,3};
  69.     bsort(array3, 10);
  70.     for(int i = 0; i < 10; i++)
  71.         printf("%d ", array3[i]);
  72.     printf("\n");
  73.  
  74.     return 0;
  75. }
  76.  
  77.  
  78. ///EJERCICIO 5
  79.  
  80.  
  81. #include <stdio.h>
  82. #include <stdlib.h>
  83.  
  84. int es_permutacion(int a[], int b[], int largo){
  85.     int aux[largo], flag = 0;
  86.     for(int i = 0; i < largo; i++) aux[i] = 0;
  87.  
  88.     for(int i = 0; i < largo; i++){
  89.         flag = 0;
  90.         for(int j = 0; j < largo; j++)
  91.             if(b[j] == a[i] && aux[j] == 0){
  92.                 aux[j]++;
  93.                 flag++;
  94.                 break;
  95.             }
  96.         if(!flag)
  97.             return 0;
  98.     }
  99.     return 1;
  100. }
  101.  
  102. int main(){
  103.     int array1[] = {1,2,3,4,5}, array2[] = {1,2,2,3,3,3,4,4,4,4}, array3[] = {4,3,2,1,4,3,2,4,3,4};
  104.     (es_permutacion(array1, array1, 5) == 1)? printf("Está todo bien.\n") : printf("OhNo.mp3\n");
  105.     (es_permutacion(array2, array3, 10) == 1)? printf("Está todo bien.\n") : printf("OhNo.mp3\n");
  106.     (es_permutacion(array1, array2, 5) == 0)? printf("Está todo bien.\n") : printf("OhNo.mp3\n");
  107.     return 0;
  108. }
  109.  
  110.  
  111.  
  112. ///EJERCICIO 10
  113. //Selection NO es estable.
  114. //Insertion SI es estable.
  115. //Bubble SI es estable.
  116.  
  117.  
  118. ///EJERCICIOS 11 - 12
  119.  
  120. #include <stdio.h>
  121. #include <stdlib.h>
  122.  
  123. typedef enum{
  124.     Random,
  125.     Primero,
  126.     Ultimo,
  127.     Mitad,
  128.     MedianaDe3,
  129. }TipoPivot;
  130.  
  131.  
  132. void swapp (int *a, int *b){
  133.     int aux = *a;
  134.     *a = *b;
  135.     *b = aux;
  136. }
  137.  
  138. void quicksortPrimero(int array[], int posI, int posF){
  139.     if(posF > posI){
  140.         int menor = posI+1, mayor = posF, pivot = array[posI];
  141.         while(menor <= mayor){
  142.             if(array[menor] < pivot){
  143.                 array[menor - 1] = array[menor];
  144.                 menor++;
  145.             }
  146.             else{
  147.                 swapp(&array[menor], &array[mayor]);
  148.                 mayor--;
  149.             }
  150.         }
  151.  
  152.         array[menor - 1] = pivot;
  153.         quicksortPrimero(array, posI, mayor - 1);
  154.         quicksortPrimero(array, menor, posF);
  155.     }
  156. }
  157.  
  158. void quicksortUltimo(int array[], int posI, int posF){
  159.     if(posF > posI){
  160.         swapp(&array[posI], &array[posF]);
  161.         int menor = posI+1, mayor = posF, pivot = array[posI];
  162.         while(menor <= mayor){
  163.             if(array[menor] < pivot){
  164.                 array[menor - 1] = array[menor];
  165.                 menor++;
  166.             }
  167.             else{
  168.                 swapp(&array[menor], &array[mayor]);
  169.                 mayor--;
  170.             }
  171.         }
  172.  
  173.         array[menor - 1] = pivot;
  174.         quicksortUltimo(array, posI, mayor - 1);
  175.         quicksortUltimo(array, menor, posF);
  176.     }
  177. }
  178.  
  179. void quicksortMitad(int array[], int posI, int posF){
  180.     if(posF > posI){
  181.         swapp(&array[posI], &array[posI + (posF-posI)/2]);
  182.         int menor = posI+1, mayor = posF, pivot = array[posI];
  183.         while(menor <= mayor){
  184.             if(array[menor] < pivot){
  185.                 array[menor - 1] = array[menor];
  186.                 menor++;
  187.             }
  188.             else{
  189.                 swapp(&array[menor], &array[mayor]);
  190.                 mayor--;
  191.             }
  192.         }
  193.  
  194.         array[menor - 1] = pivot;
  195.         quicksortMitad(array, posI, mayor - 1);
  196.         quicksortMitad(array, menor, posF);
  197.     }
  198. }
  199.  
  200. void quicksortRandom(int array[], int posI, int posF){
  201.     if(posF > posI){
  202.         srand(time(NULL));
  203.         swapp(&array[posI], &array[rand()%(posF-posI) + posI]);
  204.         int menor = posI+1, mayor = posF, pivot = array[posI];
  205.         while(menor <= mayor){
  206.             if(array[menor] < pivot){
  207.                 array[menor - 1] = array[menor];
  208.                 menor++;
  209.             }
  210.             else{
  211.                 swapp(&array[menor], &array[mayor]);
  212.                 mayor--;
  213.             }
  214.         }
  215.  
  216.         array[menor - 1] = pivot;
  217.         quicksortRandom(array, posI, mayor - 1);
  218.         quicksortRandom(array, menor, posF);
  219.     }
  220. }
  221.  
  222. int decidirMediana(int array[], int a, int b, int c){
  223.     if(array[a] <= array[b]){
  224.         if(array[b] <= array[c])
  225.             return b;
  226.         if (array[c] >= array[a])
  227.             return c;
  228.         return a;
  229.     }
  230.     if(array[c] >= array[a])
  231.         return a;
  232.     if(array[c] >= array[b])
  233.         return c;
  234.     return b;
  235. }
  236.  
  237. void quicksortMediana(int array[], int posI, int posF){
  238.     if(posF > posI){
  239.         int mediana = decidirMediana(array, posI, posI + (posF - posI) / 2, posF);
  240.         swapp(&array[posI], &array[mediana]);
  241.         int menor = posI+1, mayor = posF, pivot = array[posI];
  242.         while(menor <= mayor){
  243.             if(array[menor] < pivot){
  244.                 array[menor - 1] = array[menor];
  245.                 menor++;
  246.             }
  247.             else{
  248.                 swapp(&array[menor], &array[mayor]);
  249.                 mayor--;
  250.             }
  251.         }
  252.  
  253.         array[menor - 1] = pivot;
  254.         quicksortMediana(array, posI, mayor - 1);
  255.         quicksortMediana(array, menor, posF);
  256.     }
  257. }
  258.  
  259. void quicksort(int array[], int largo, TipoPivot pivot){
  260.     switch(pivot){
  261.     case Primero:
  262.         quicksortPrimero(array, 0, largo-1);
  263.         break;
  264.     case Ultimo:
  265.         quicksortUltimo(array, 0, largo-1);
  266.         break;
  267.     case Mitad:
  268.         quicksortMitad(array, 0, largo-1);
  269.         break;
  270.     case Random:
  271.         quicksortRandom(array, 0, largo-1);
  272.         break;
  273.     case MedianaDe3:
  274.         quicksortMediana(array, 0, largo-1);
  275.         break;
  276.     }
  277. }
  278.  
  279. int main(){
  280.     int array[] = {0,14,-7,9,4,59,-20,1,2,3};
  281.     quicksort(array, 10, MedianaDe3);
  282.     for(int i = 0; i < 10; i++)
  283.         printf("%d ", array[i]);
  284.     printf("\n");
  285.     return 0;
  286. }
  287.  
  288.  
  289.  
  290.  
  291. ///EJERCICIO 14
  292.  
  293.  
  294. #include <stdio.h>
  295. #include <stdlib.h>
  296.  
  297. void swapp (int *a, int *b){
  298.     int aux = *a;
  299.     *a = *b;
  300.     *b = aux;
  301. }
  302.  
  303. void hsort(int array[], int largo){
  304. ///Armado del heap.
  305.     for(int i = 0; i < largo; i++)
  306.         for(int j = i; j > 0; j = (j-1) / 2){
  307.             if(array[j] > array[(j-1)/2])
  308.                 swapp(&array[j], &array[(j-1) / 2]);
  309.             else break;
  310.         }
  311. ///Eliminaciones del máximo.
  312.     for(int i = largo - 1; i > 0; i--){
  313.         swapp(&array[0], &array[i]);
  314.         for(int j = 0; j < i/2 ;){
  315.             if(j*2 + 2 < i){
  316.                 if(array[j] < array[j*2 + 1] || array[j] < array[j*2 + 2]){
  317.                     if(array[j*2 + 1] > array[j*2 + 2]){
  318.                         swapp(&array[j], &array[j*2 + 1]);
  319.                         j = j*2 + 1;
  320.                     }
  321.                     else{
  322.                         swapp(&array[j], &array[j*2 + 2]);
  323.                         j = j*2 + 2;
  324.                     }
  325.                 }
  326.                 else break;
  327.             }
  328.             else{
  329.                 if(array[j] < array[j*2 + 1]){
  330.                     swapp(&array[j], &array[j*2 + 1]);
  331.                     j = j*2 + 1;
  332.                 }
  333.                 else break;
  334.             }
  335.         }
  336.     }
  337. }
  338.  
  339. int main(){
  340.     int array[] = {0,14,-7,9,4,59,-20,1,2,3};
  341.     hsort(array, 10);
  342.     for(int i = 0; i < 10; i++)
  343.         printf("%d ", array[i]);
  344.     printf("\n");
  345.     return 0;
  346. }
  347.  
  348.  
  349.  
  350. ///EJERCICIO 16
  351.  
  352.  
  353. #include <stdio.h>
  354. #include <stdlib.h>
  355.  
  356. void swapp (int *a, int *b){
  357.     int aux = *a;
  358.     *a = *b;
  359.     *b = aux;
  360. }
  361.  
  362. void msortAux(int array[], int posI, int posF){
  363.     if(posI < posF){
  364.         int mitad = posI + (posF - posI)/2;
  365.         msortAux(array, posI, mitad);
  366.         msortAux(array, mitad + 1, posF);
  367.         int arrayAux[posF - posI + 1], inicioIzq = posI, inicioDer = mitad + 1;
  368.         for(int i = 0; i <= posF - posI + 1; i++){
  369.             if(inicioIzq == mitad + 1)
  370.                 arrayAux[i] = array[inicioDer++];
  371.             else if(inicioDer == posF + 1)
  372.                 arrayAux[i] = array[inicioIzq++];
  373.             else{
  374.                 if(array[inicioIzq] <= array[inicioDer])
  375.                     arrayAux[i] = array[inicioIzq++];
  376.                 else
  377.                     arrayAux[i] = array[inicioDer++];
  378.             }
  379.         }
  380.         for(int i = 0; i <= posF - posI + 1; i++)
  381.             array[posI + i] = arrayAux[i];
  382.     }
  383. }
  384.  
  385.  
  386. void msort(int array[], int largo){
  387.     msortAux(array, 0, largo - 1);
  388. }
  389.  
  390. int main(){
  391.     int array[] = {0,14,-7,9,4,59,-20,1,2,3};
  392.     msort(array, 10);
  393.     for(int i = 0; i < 10; i++)
  394.         printf("%d ", array[i]);
  395.     printf("\n");
  396.     return 0;
  397. }
Add Comment
Please, Sign In to add comment
Public Pastes
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!