Algoritmi

Merge

Fusione di due sequenze ordinate

L'algoritmo in questione fonde due sequenze di interi, entrambe con gli elementi in ordine ascendente, in un'unica sequenza ordinata.
Per fondere due array A di m elementi e B di n elementi, dovremo effetture un confronto tra gli elementi dei due vettori e riportare gli elementi ordinati nel terzo vettore C.
Supponiamo di voler fondere i seguenti array:

Il confronto tra A(1) e B(1) ci permette di assegnare il primo elemento di C.

Dopo aver posto il primo elemento ci occorre un modo per decidere quale elemento colllocare successivamente.
Il modo più semplice è quello di confrontare l'elemento successivo dell'array dal quale è stato effettuato l'ultimo prelievo, con l'elemento corrente dell'altro. Nel nostro caso quindi poichè il primo elemento di C è stato prelevato da B confronteremo l'elemento B(2) con A(1) e così via. Quando avremo prelevato tutti gli elementi dell'array più corto basterà copiare tutti gli elementi residui dell'altro e non sarà quindi necessario effettuare altresì dei confronti che dal punto di vista numerico risulatno onerosi.

Una struttura che si può usare è la seguente:

1. finchè i <= m e j <= n
   (a) confronta A(i) con B(j) e colloca nell'array C l'elemento minore della coppia;
   (b) aggiorna i puntatori appropriati;
2. se i < m
   (a) copia in C la parte rimanente di A
   altrimenti
   (b) copia in C la parte rimanente di B.

Di seguito è riportato l'implementazione di tale lagoritmo in fortran:

       SUBROUTINE SHORTMERGE(A,B,C,N,M,K)
C Routine per la fusione ordinata di due vettori
      INTEGER A(100),B(100),C(100)
	  INTEGER N,M
	  INTEGER K,I,J,W
C Corpo del programma
C Inizializzazione delle variabili
      I = 1
	  K = 1
	  J = 1 
12    CONTINUE
C Ciclo While da ripetere fin quando i<=m
      IF(A(I).LE.B(J))THEN
	   C(K) = A(I)
	   I=I+1
	  ELSE
	   C(K) = B(J)
	   J=J+1
      ENDIF
      K=K+1
	  W=K	
	  IF(I.LE.N)GOTO 12
	  DO 20 K=W,N+M
	   C(K) = B(J) 
	   J=J+1      
20    CONTINUE
      K=K-1
	  RETURN
	  END

• » Invia tramite EMAIL
• » Versione per la STAMPA
• » Le vostre opinioni

I link correlati all'argomento

• ABS algorithm.
• I numeri di Fibonacci
• L'algoritmo dei minimi quadrati
• L'algoritmo di Eulero