Implementazioni di algoritmi/Merge sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Annullate le modifiche di 151.73.222.38 (discussione), riportata alla versione precedente di 79.52.193.187 |
|||
Riga 52:
===[[w:C (linguaggio)|C]]===
///chiamata a funzione:
mergeSort(vettore);
Questa versione di mergeSort lavora su una struttura di tipo nodo che contiene una chiave di ordinamento (key) e un pacchetto di dati (data).
Nelle chiamate ricorsive non vengono mai dichiarati nuovi vettori.
Vengono dichiarate solo poche variabili nello Stack.
la funzione mergeSort si occupa di allocare un solo vettore ausiliario e alla fine di eliminarlo.
la funzione Msort esegue il cosiddetto "divide";
La funzione merge "impacchetta il vettore".
typedef struct data{
char*some;
int data;
} DATA;
typedef struct _nodo{
int key;
DATA data;
}nodo;
int n;
void merge(nodo*a,nodo*aux,int left,int right,int rightEnd){
int i,num,temp,leftEnd=right-1;
temp=left;
num=rightEnd-left+1;
while((left<=leftEnd)&&(right<=rightEnd)){
if(a[left].key<=a[right].key){
aux[temp++]=a[left++];
}
else{
aux[temp++]=a[right++];
}
}
while(left<=leftEnd){
aux[temp++]=a[left++];
}
while(right<=rightEnd){
aux[temp++]=a[right++];
}
for (i=1;i<=num;i++,rightEnd--){
a[rightEnd]=aux[rightEnd];
}
}
void mSort(nodo*a,nodo*aux,int left,int right){
int center;
if (left<right){
center=(left+right)/2;
mSort(a,aux,left,center);
}
}
void mergeSort(nodo*p){
nodo*temp=(nodo*)malloc(sizeof(nodo)*n);
mSort(p,temp,0,n-1);
int i;
free(temp);
}
===[[w:C (linguaggio)|C (metodo iterativo)]]===
| |||