Salve a tutti. Devo implementare l'algoritmo dell Heap sort in C e dopo alcune prove mi rivolgo qui.
In output dobbiamo avere un vettore ordinato del tipo 1 3 5 7 99 123.....
Tale algoritmo crea prima l'heap e poi lo ordina quindi sono due fasi distinte.
Vorrei capire la prima fase, ovvera quella in cui abbiamo in output: 99,88,90,40,12,67,55.
dove ogni A
> A[2i] e 2i+1.
il codice da me elaborato funziona, ma funziona solo su un vettore di 3 elementi. nel momento che in #define N inserisci invece di 3 il valore 7 o altro, non funziona più niente.
idee??
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 3
int riempi_vettore(int *A, int n){
int i;
srand(time(NULL));
for(i=0;i<n;i++){
A[i]=rand()%20; // casuali tra 0 e 20
}
}
int stampa_vettore(int *A, int n){
int i;
for(i=0;i<n;i++){ printf("%d ", A[i]); }
}
int sinistro(int i){
i=((2*i)+1);
return i;
}
int destro(int i){
i=(2*(i+1));
return i;
}
int heapify(int *A, int i){
int l,r;
int maggiore,tmp;
l=sinistro(i);
r=destro(i);
if( l<N && A[l] > A[i] ){
maggiore=l;
}
else{ maggiore=i; }
if( r<N && A[r] > A[maggiore] ){
maggiore=r;
}
if( maggiore!=i){
tmp=A[i];
A[i]=A[maggiore];
A[maggiore]=tmp;
heapify(A,maggiore);
}
}
int main(){
int vettore[N];
riempi_vettore(vettore,N);
stampa_vettore(vettore,N);
heapify(vettore,0);
printf("\n ordinato \n\n");
stampa_vettore(vettore,N);
system("pause");
}