Alx09

SDA EXAMEN HELPER

Jan 18th, 2021 (edited)
654
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2.  
  3. #include <conio.h>
  4.  
  5. #include <time.h>
  6.  
  7. #include <stdlib.h>
  8.  
  9. //#include <cstdbool>
  10.  
  11. #include <math.h>
  12.  
  13. int N, count = 1;
  14. void swap(int* a, int* b)
  15. {
  16.     int t = *a;
  17.     *a = *b;
  18.     *b = t;
  19. }
  20. void citire(int a[], int n)
  21. {
  22.     int i;
  23.     printf("Dati cele %d numere: ", n);
  24.     for (i = 0; i < n; i++)
  25.         scanf("%d", &a[i]);
  26. }
  27.  
  28. void afisare(int a[], int n)
  29. {
  30.     int i;
  31.     for (i = 0; i < n; i++)
  32.         printf("%d ", a[i]);
  33.     printf("\n");
  34. }
  35. void insertie(int a[], int n)
  36. {
  37.     int i, j, aux;
  38.     for (i = 1; i < n; i++)
  39.     {
  40.         aux = a[i];
  41.         j = i - 1;
  42.         while (j >= 0 && a[j] > aux)
  43.         {
  44.             a[j + 1] = a[j];
  45.             j = j - 1;
  46.         }
  47.  
  48.         a[j + 1] = aux;
  49.         printf("Etapa %d: ", i);
  50.         afisare(a, n);
  51.     }
  52. }
  53.  
  54. int cautareBinara(int a[], int cautat, int s, int d)
  55. {
  56.     if (d <= s)
  57.     {
  58.         if (cautat > a[s])
  59.             return (s + 1);
  60.         else
  61.             return s;
  62.     }
  63.     int m = (s + d) / 2;
  64.     if (cautat == a[m])
  65.         return m + 1;
  66.     if (cautat > a[m])
  67.         return cautareBinara(a, cautat, m + 1, d);
  68.     return cautareBinara(a, cautat, s, m - 1);
  69. }
  70.  
  71. void insertieBinara(int a[], int n)
  72. {
  73.     int i, j, aux, loc;
  74.     for (i = 1; i < n; i++)
  75.     {
  76.         j = i - 1;
  77.         aux = a[i];
  78.         loc = cautareBinara(a, aux, 0, j);
  79.         while (j >= loc)
  80.         {
  81.             a[j + 1] = a[j];
  82.             j--;
  83.         }
  84.         a[j + 1] = aux;
  85.         printf("\nEtapa %d: ", i);
  86.         afisare(a, n);
  87.     }
  88. }
  89.  
  90. void selectie(int a[], int n)
  91. {
  92.     int i, j, k_min, aux;
  93.     for (i = 0; i < n - 1; i++)
  94.     {
  95.         k_min = i;
  96.         aux = a[i];
  97.         for (j = i + 1; j < n; j++)
  98.             if (a[j] < a[k_min])
  99.             {
  100.                 k_min = j;
  101.                 aux = a[k_min];
  102.             }
  103.         a[k_min] = a[i];
  104.         a[i] = aux;
  105.         printf("\nEtapa %d: ", i + 1);
  106.         afisare(a, n);
  107.     }
  108. }
  109. void selectiePerformanta(int a[], int n)
  110. {
  111.     int i, j, k_min, aux;
  112.     for (i = 0; i < n - 1; i++)
  113.     {
  114.         k_min = i;
  115.         for (j = i + 1; j < n; j++)
  116.             if (a[j] < a[k_min])
  117.                 k_min = j;
  118.         aux = a[k_min];
  119.         a[k_min] = a[i];
  120.         a[i] = aux;
  121.         printf("\nEtapa %d: ", i + 1);
  122.         afisare(a, n);
  123.     }
  124. }
  125.  
  126. void bubbleSort(int a[], int n)
  127. {
  128.     int i, j, aux;
  129.     for (i = 1; i < n; i++)
  130.     {
  131.         for (j = n - 1; j >= i; j--)
  132.             if (a[j - 1] > a[j])
  133.             {
  134.                 aux = a[j - 1];
  135.                 a[j - 1] = a[j];
  136.                 a[j] = aux;
  137.             }
  138.         printf("\nEtapa %d: ", i);
  139.         afisare(a, n);
  140.     }
  141.  
  142. }
  143.  
  144. void shakeSort(int a[], int n)
  145. {
  146.     int  j, k, s, d, aux, count = 1;
  147.     s = 1;
  148.     d = n - 1;
  149.     k = n - 1;
  150.     do
  151.     {
  152.         for (j = d; j >= s; j--)
  153.             if (a[j - 1] > a[j])
  154.             {
  155.                 aux = a[j - 1];
  156.                 a[j - 1] = a[j];
  157.                 a[j] = aux;
  158.                 k = j;
  159.             }
  160.         s = k + 1;
  161.         for (j = s; j <= d; j++)
  162.             if (a[j - 1] > a[j])
  163.             {
  164.                 aux = a[j - 1];
  165.                 a[j - 1] = a[j];
  166.                 a[j] = aux;
  167.                 k = j;
  168.             }
  169.         d = k - 1;
  170.         printf("\nEtapa %d: ", count);
  171.         afisare(a, n);
  172.         count++;
  173.  
  174.     } while (s <= d);
  175. }
  176. void binsort(int a[], int n)
  177. {
  178.     int i, aux;
  179.     for (i = 0; i < n; i++)
  180.     {
  181.         while (a[i] != i)
  182.         {
  183.             aux = a[a[i]];
  184.             a[a[i]] = a[i];
  185.             a[i] = aux;
  186.         }
  187.         printf("Etapa %d: ", i + 1);
  188.         afisare(a, n);
  189.     }
  190. }
  191.  
  192. void shellsort(int a[], int n)
  193. {
  194.     int i, j, aux, l, k;
  195.     int h[3] = { 3,2,1 };
  196.     for (l = 0; l < 3; l++)
  197.     {
  198.         k = h[l];
  199.         for (i = k; i < n; i++)
  200.         {
  201.             aux = a[i];
  202.             j = i - k;
  203.             while (j >= 0 && aux < a[j])
  204.             {
  205.                 a[j + k] = a[j];
  206.                 j = j - k;
  207.             }
  208.             a[j + k] = aux;
  209.         }
  210.         printf("Trecerea %d: ", l + 1);
  211.         afisare(a, n);
  212.     }
  213. }
  214.  
  215. void heapify(int arr[], int n, int i)
  216. {
  217.     int aux;
  218.     int largest = i; // Initialize largest as root
  219.     int l = 2 * i + 1; // left = 2*i + 1
  220.     int r = 2 * i + 2; // right = 2*i + 2
  221.  
  222.     // If left child is larger than root
  223.     if (l < n && arr[l] > arr[largest])
  224.         largest = l;
  225.  
  226.     // If right child is larger than largest so far
  227.     if (r < n && arr[r] > arr[largest])
  228.         largest = r;
  229.     // If largest is not root
  230.     if (largest != i)
  231.     {
  232.         aux = arr[i];
  233.         arr[i] = arr[largest];
  234.         arr[largest] = aux;
  235.  
  236.         // Recursively heapify the affected sub-tree
  237.         heapify(arr, n, largest);
  238.     }
  239. }
  240.  
  241. // main function to do heap sort
  242. void heapSort(int arr[], int n)
  243. {
  244.     int aux;
  245.     // Build heap (rearrange array)
  246.     for (int i = n / 2 - 1; i >= 0; i--)
  247.     {
  248.         heapify(arr, n, i);
  249.         printf("Etapa %da: ", n / 2 - i);
  250.         afisare(arr, n);
  251.     }
  252.     printf("Forma De ansablu invers!\n");
  253.     // One by one extract an element from heap
  254.     for (int i = n - 1; i > 0; i--)
  255.     {
  256.         // Move current root to end
  257.         aux = arr[0];
  258.         arr[0] = arr[i];
  259.         arr[i] = aux;
  260.         printf("Etapa %db: ", n - i);
  261.         afisare(arr, n);
  262.         // call max heapify on the reduced heap
  263.         heapify(arr, i, 0);
  264.     }
  265. }
  266. int partition(int arr[], int low, int high)
  267. {
  268.     int pivot = arr[(high + low) / 2];
  269.     while (low <= high)
  270.     {
  271.         while (arr[low] < pivot)
  272.             low++;
  273.         while (arr[high] > pivot)
  274.             high--;
  275.         if (low <= high)
  276.         {
  277.             swap(&arr[low], &arr[high]);
  278.             low++;
  279.             high--;
  280.         }
  281.     }
  282.     return high;
  283. }
  284.  
  285. void quickSort(int a[], int s, int d)
  286. {
  287.     if (s < d)
  288.     {
  289.         int pi = partition(a, s, d);
  290.         printf("Etapa %d: ", count);
  291.         count++;
  292.         afisare(a, N);
  293.         quickSort(a, s, pi - 1);
  294.         quickSort(a, pi, d);
  295.     }
  296. }
  297. int biti(int x, int k, int j)
  298. {
  299.     return (x >> k)&~(~0 << j);
  300. }
  301. void radix_interschimbare(int a[], int s, int d, int b)
  302. {
  303.     int i, j, aux;
  304.     if (d > s && b >= 0)
  305.     {
  306.         i = s;
  307.         j = d;
  308.         do
  309.         {
  310.             while (i < j && biti(a[i], b, 1) == 0)
  311.                 i++;
  312.             while (i < j && biti(a[j], b, 1) == 1)
  313.                 j--;
  314.             aux = a[i];
  315.             a[i] = a[j];
  316.             a[j] = aux;
  317.  
  318.         } while (i != j);
  319.         printf("Etapa %d: ", count);
  320.         count++;
  321.         afisare(a, N);
  322.         if (biti(a[d], b, 1) == 0)
  323.             j++;
  324.         radix_interschimbare(a, s, j - 1, b - 1);
  325.         radix_interschimbare(a, j, d, b - 1);
  326.     }
  327. }
  328. void radix_direct(int a[], int n)
  329. {
  330.     int b, T[100], Numar[100], m, k, i, t;
  331.     b = sizeof(int) * 8;
  332.     m = 4;
  333.     for (t = 0; t < b / m; t++)
  334.     {
  335.         for (i = 0; i < pow(2, m); i++)
  336.             Numar[i] = 0;
  337.         for (i = 0; i < n; i++)
  338.         {
  339.             k = biti(a[i], t*m, m);
  340.             Numar[k]++;
  341.         }
  342.         for (i = 1; i < pow(2, m); i++)
  343.             Numar[i] = Numar[i] + Numar[i - 1];
  344.         for (i = n - 1; i >= 0; i--)
  345.         {
  346.             k = biti(a[i], t*m, m);
  347.             T[Numar[k] - 1] = a[i];
  348.             Numar[k]--;
  349.  
  350.         }
  351.         printf("Etapa %d: ", t + 1);
  352.         afisare(T, n);
  353.         for (i = 0; i < n; i++)
  354.             a[i] = T[i];
  355.     }
  356. }
  357. int main()
  358. {
  359.     int a[] = { 2,  14 , 9 , 7 , 11,  4 , 17 , 0 , 5 , 8 }, n, opt, b; // in a introduceti numerele din cerinta cu virgula intre ele
  360.     do
  361.     {
  362.         printf("1.Sortare prin insertie\n");
  363.         printf("2.Sortare prin selectie\n");
  364.         printf("3.Sortare Bubblesort\n");
  365.         printf("4.Shakesort\n");
  366.         printf("5.Binsort\n");
  367.         printf("6.Shellsort\n");
  368.         printf("7.Heap sort\n");
  369.         printf("8.Quicksort\n");
  370.         printf("9.Radix interschimbare\n");
  371.         printf("10.Radix direct\n");
  372.         printf("0.Iesire\n");
  373.         printf("Dati optiunea: ");
  374.         scanf("%d", &opt);
  375.         system("cls");
  376.         n = sizeof(a) / 4;
  377.         switch (opt)
  378.         {
  379.         case 1:
  380.             printf("SORTAREA PRIN INSERTIE\n");
  381.             insertie(a, n);
  382.             printf("\nTabloul dupa sortare:\n");
  383.             afisare(a, n);
  384.             break;
  385.         case 2:
  386.             printf("\nSORTAREA PRIN SELECTIE\n");
  387.             selectie(a, n);
  388.             printf("\nTabloul dupa sortare:\n");
  389.             afisare(a, n);
  390.             break;
  391.         case 3:
  392.             printf("\nBUBLE SORT\n");
  393.            bubbleSort(a, n);break;
  394.         case 4:
  395.             printf("\nSHAKE SORT\n");
  396.             shakeSort(a, n);break;
  397.         case 5:
  398.             printf("\nBinsort\n");
  399.             binsort(a, n);
  400.             break;
  401.         case 6:
  402.             printf("Shellsort");
  403.             shellsort(a, n);
  404.             break;
  405.         case 7:
  406.             printf("\nHEAPSORT\n");
  407.             heapSort(a, n);
  408.             break;
  409.         case 8:
  410.             printf("\nQUICKSORT\n");
  411.            
  412.             N = n;
  413.             count = 1;
  414.             quickSort(a, 0, n - 1);
  415.             break;
  416.         case 9:
  417.             printf("\nRADIX INTERSCHIMBARE\n");
  418.             b = sizeof(int) * 8;
  419.             N = n;
  420.             count = 1;
  421.             radix_interschimbare(a, 0, n - 1, b - 1);
  422.  
  423.             break;
  424.         case 10:
  425.             printf("\nRADIX DIRECT\n");
  426.             radix_direct(a, n);
  427.             break;
  428.         case 0:
  429.             printf("\nAti oprit consola interactiva\n");
  430.             break;
  431.         default:
  432.             printf("\nOPTIUNE INVALIDA\n");
  433.             break;
  434.  
  435.         }
  436.         system("pause");
  437.     } while (opt != 0);
  438.     getch();
  439.     return 0;
  440. }
RAW Paste Data