Heap sort problemi.

di il
1 risposte

Heap sort problemi.

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");
}

1 Risposte

  • Re: Heap sort problemi.

    Premetto che non ho analizzato il tuo codice ma potresti cominciare col togliere quella costante N = 3 e acquisire un numero da tastiera ogni volta, allocando gli array dinamicamente. Se tenti di allocare 7 numeri in un array di grandezza 3 è normale che qualcosa non quadra.
Devi accedere o registrarti per scrivere nel forum
1 risposte