/* File: ordmergo.c */ /* Time-stamp: "2001-05-25 16:08:12 calvanes" */ /* Scopo: funzioni sui vettori */ void MergeVettoreOttimizzato(TipoVettore A, int iniziale, int mediano, int finale) /* Fonde i due sottovettori ordinati di A da iniziale a mediano e da mediano+1 a finale in un unico sottovettore ordinato. Versione ottimizzata che evita di effettuare una doppia copia degli elementi finali di uno dei sottovettori. */ { TipoVettore B; /* vettore di appoggio */ int primo, secondo, appoggio, i; primo = iniziale; secondo = mediano + 1; appoggio = iniziale; while (primo <= mediano && secondo <= finale) { if (A[primo] <= A[secondo]) { B[appoggio] = A[primo]; primo++; } else { B[appoggio] = A[secondo]; secondo++; } appoggio++; } /* parte finale ottimizzata */ if (secondo > finale) /* e` finito prima il secondo sottovettore; copia da A in A stesso tutti gli elementi fino a mediano, incominciando dal basso */ for (i = mediano; i >= primo; i--) { A[finale] = A[i]; finale--; } /* NON c'e' il ramo else */ /* copia tutti gli elementi da iniziale a appoggio-1 da B ad A */ for (i = iniziale; i <= appoggio - 1; i++) A[i] = B[i]; } /* MergeVettoreOttimizzato */ void MergeRicorsivoOttimizzato(TipoVettore A, int iniziale, int finale) /* Ordina gli elementi del vettore A di indice compreso tra iniziale e finale usando l'algoritmo di ordinamento per fusione. Utilizza la versione ottimizzata della funzione per effettuare il merge. */ { int mediano; int i; if (iniziale < finale) { mediano = (iniziale + finale) / 2; MergeRicorsivoOttimizzato(A, iniziale, mediano); MergeRicorsivoOttimizzato(A, mediano + 1, finale); /* printf("merge %d-%d [ ", iniziale, mediano); for (i = iniziale; i <= mediano; i++) printf("%d ", A[i]); printf("] con %d-%d [ ", mediano + 1, finale); for (i = mediano + 1; i <= finale; i++) printf("%d ", A[i]); printf("] ==> [ "); */ MergeVettoreOttimizzato(A, iniziale, mediano, finale); /* for (i = iniziale; i<= finale; i++) printf("%d ", A[i]); printf("]\n"); */ } } /* MergeRicorsivo */ void MergeSortOttimizzato(TipoVettore A, int n) /* Ordina i primi n elementi del vettore A usando l'algoritmo di ordinamento per fusione. Utilizza la versione ottimizzata della funzione per effettuare il merge. */ { MergeRicorsivoOttimizzato(A, 0, n-1); } /* MergeSortOttimizzato */