# [LV5] Algoritmi - Heap sort

May 8th, 2018
114
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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. }