-
Notifications
You must be signed in to change notification settings - Fork 51
/
Copy pathHeapSort.c
99 lines (88 loc) · 1.65 KB
/
HeapSort.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <stdlib.h>
#include <stdio.h>
#define MAX 300
int main(void) {
int n, V[MAX];
n = leggi_array(V);
HeapSort(V, n);
stampa_array(V, n);
return(0);
}
//scambia il valore delle due variabili.
void scambia(int *x, int *y) {
int z;
z = *x;
*x = *y;
*y = z;
return;
}
/*
* Legge in input il numero n ed n numeri interi
* che memorizza nell'array. Restituisce il numero
* di elementi letti (n).
*/
int leggi_array(int V[]) {
int n, i;
printf("Numero di elementi: ");
scanf("%d", &n);
printf("Inserisci %d numeri: ", n);
for (i=0; i<n; i++)
scanf("%d", &V[i]);
return(n);
}
void stampa_array(int V[], int n) {
int i;
for (i=0; i<n; i++) {
printf("%d ", V[i]);
}
printf("\n");
return;
}
//inserisce l'elemento x nell'heap H.
void Inserisci(int x, int H[]) {
int l;
l = H[0]+1;
H[0] = H[0]+1;
H[l] = x;
while (l>1 && H[l/2]<H[l]) {
scambia(&H[l], &H[l/2]);
l = l/2;
}
return;
}
/*
* restituisce il massimo elemento
* dell'heap H (la radice) e ricostruisce la
* struttura di heap.
*/
int EstraiMax(int H[]) {
int max, i;
max = H[1];
H[1] = H[H[0]];
H[0] = H[0]-1;
i = 1;
while (2*i<H[0] && (H[i]<H[2*i] || H[i]<H[2*i+1])) {
if (H[2*i] > H[2*i+1]) {
scambia(&H[i], &H[2*i]);
i = 2*i;
} else {
scambia(&H[i], &H[2*i+1]);
i = 2*i+1;
}
}
if (2*i == H[0] && H[i] < H[2*i])
scambia(&H[i], &H[2*i]);
return(max);
}
/*
* ordina l'array A mediante l'algoritmo Heap Sort.
*/
void HeapSort(int A[], int n) {
int i, H[MAX];
H[0] = 0;
for (i=0; i<n; i++)
Inserisci(A[i], H);
for (i=n-1; i>=0; i--)
A[i] = EstraiMax(H);
return;
}