PDA

Visualizza la versione completa : [C] merge sort


SSSS90
29-05-2014, 15:55
Salve questo è il codice dell'algoritmo di merge sort,non capisco che significa passare alla funzione merge un vettore più una costante m..non ne capisco il senso....cioè:


merge_sort (a+m , n -m , temp );


void merge_sort ( TInfo a [] , int n, TInfo temp []) {
int i, m=n /2;
if (n <2)
return;
merge_sort (a , m , temp );
merge_sort (a+m , n -m , temp );
merge (a , m , a+m , n -m , temp );
for(i =0; i <n; i ++)
a[i ]= temp [i ];
}

Alex'87
29-05-2014, 17:02
La costante senza senso è l'elemento pivot.

La teoria che sta dientro al merge sort la conosci?

http://en.wikipedia.org/wiki/Merge_sort

SSSS90
29-05-2014, 17:13
grz alex..sei sempre gentile...facciamo prima se ti dico la parte che non capisco dal mio testo:

la seconda chiamata ricorsiva(quella in questione) ordina la seconda parte dell'array-Si noti che in questo caso come array da ordinare viene passato a+m che in base alla regole dell'aritmetica dei puntatori corrisponde all'indirizzo dell'elemento a[m],(??)il primo elemento della seconda parte di a(ricordiamo che in c gli array sono sempre passati per riferimento, e il parametro effettivo corrisponde all'indirizzo del primo elemento dell'array.....

sta forse cercando di dirmi che attraverso questo m riesco ad incrementare il riferimento della prima cella di memoria e passare di cella in cella....

tu che ne pensi..io non capisco..

Scara95
30-05-2014, 15:05
a+m corrisponde a &a[m]

In sostanza passa la seconda metà dell'array.

Il mergesort infatti funziona dividendo a metà l'array fino a giungere ad avere un solo elemento e poi ricomponendoli ordinatamente. (merge)

Loading