Advertisement
Domy131097

[LV5] Algoritmi - Heap sort

May 8th, 2018
114
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.84 KB | None
  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <time.h>
  6.  
  7. #define randnum(min, max) \
  8.         ((rand() % (int)(((max) + 1) - (min))) + (min))
  9.  
  10. int velicinaHrpe = 0;
  11.  
  12. void unosNiza(int *V, int  n);
  13. void heap_sort(int *V, int n);
  14. void bubble_sort(int *V, int n);
  15. void ispis(int *V);
  16. void merge_sort(int a[], int i, int j);
  17.  
  18. int main() {
  19.     int n, *V = NULL, *B = NULL, *M = NULL;
  20.     time_t t = NULL;
  21.     printf("Unesite velicinu polja:\n");
  22.     scanf("%d", &n);
  23.     velicinaHrpe = n;
  24.     V = (int *)malloc(n * sizeof(int));
  25.     B = (int *)malloc(n * sizeof(int));
  26.     M = (int *)malloc(n * sizeof(int));
  27.     unosNiza(V, n);
  28.     B = V; M = V;
  29.     t = clock();
  30.     bubble_sort(B, n);
  31.     t = clock() - t;
  32.     printf("Vrijeme sortiranja Bubble metodom: %dms.\n", t);
  33.     t = clock();
  34.     heap_sort(V, n);
  35.     t = clock() - t;
  36.     printf("Vrijeme sortiranja Heapsort metodom: %dms.\n", t);
  37.     velicinaHrpe = n;
  38.    
  39.     t = clock();
  40.     merge_sort(M, 0, n - 1);
  41.     t = clock() - t;
  42.     printf("Vrijeme sortiranja Merge metodom: %dms.\n", t);
  43.  
  44.     return 1;
  45. }
  46.  
  47. void unosNiza(int *V, int  n) {
  48.     for (int i = 0; i < n; i++) {
  49.         V[i] = randnum(0, 500);
  50.         //printf("%d ", V[i]);
  51.     }
  52. }
  53.  
  54. int lijevi(int i) {
  55.     return (2 * i) + 1;
  56. }
  57.  
  58. int desni(int i) {
  59.     return (2 * i) + 2;
  60. }
  61.  
  62. void zamjena(int *x, int *y) {
  63.     int temp = *x;
  64.     *x = *y;
  65.     *y = temp;
  66. }
  67.  
  68. void ispis(int *V) {
  69.     for (int i = 0; i < velicinaHrpe; i++) {
  70.         printf("%d\t", V[i]);
  71.     }
  72.     printf("\n");
  73. }
  74.  
  75. void uhrpi(int *A, int i) {
  76.     int l = lijevi(i), d = desni(i), najveci;
  77.     if ((A[l] > A[i]) && (l < velicinaHrpe)) najveci = l;
  78.     else najveci = i;
  79.     if ((A[d] > A[najveci]) && (d < velicinaHrpe)) najveci = d;
  80.     if (najveci != i) {
  81.         //ispis(A);
  82.         zamjena(&A[najveci], &A[i]);
  83.         uhrpi(A, najveci);
  84.     }
  85. }
  86.  
  87. void max_hrpa(int *A) {
  88.     for (int i = (velicinaHrpe - 1) / 2; i >= 0; i--) {
  89.         uhrpi(A, i);
  90.         //ispis(A);
  91.     }
  92. }
  93.  
  94. void heap_sort(int *V, int n) {
  95.     max_hrpa(V);
  96.     for (int i = velicinaHrpe; i > 0; i--) {
  97.         //ispis(V);
  98.         zamjena(&V[0], &V[velicinaHrpe - 1]);
  99.         velicinaHrpe--;
  100.         uhrpi(V, 0);
  101.     }
  102. }
  103.  
  104. void bubble_sort(int *V, int n) {
  105.     for (int i = 0; i < n - 1; i++) {
  106.         for (int j = 0; j < n - 1 - i; j++) {
  107.             if (V[j + 1] < V[j]) zamjena(&V[j + 1], &V[j]);
  108.         }
  109.     }
  110. }
  111.  
  112. void merge(int a[], int i1, int j1, int i2, int j2)
  113. {
  114.     int* temp;
  115.     temp = (int*)malloc(velicinaHrpe * sizeof(int));
  116.     int i, j, k;
  117.     i = i1;
  118.     j = i2;
  119.     k = 0;
  120.  
  121.     while (i <= j1 && j <= j2)
  122.     {
  123.         if (a[i]<a[j])
  124.             temp[k++] = a[i++];
  125.         else
  126.             temp[k++] = a[j++];
  127.     }
  128.  
  129.     while (i <= j1)
  130.         temp[k++] = a[i++];
  131.  
  132.     while (j <= j2)
  133.         temp[k++] = a[j++];
  134.  
  135.  
  136.     for (i = i1, j = 0; i <= j2; i++, j++)
  137.         a[i] = temp[j];
  138.     free(temp);
  139. }
  140.  
  141. void merge_sort(int a[], int i, int j)
  142. {
  143.     int mid;
  144.  
  145.     if (i<j)
  146.     {
  147.         mid = (i + j) / 2;
  148.         merge_sort(a, i, mid);
  149.         merge_sort(a, mid + 1, j);
  150.         merge(a, i, mid, mid + 1, j);
  151.     }
  152. }
Advertisement
RAW Paste Data Copied
Advertisement