Merge Sort

Generale:

 

Il Merge sort e' un algoritmo di ordinamento ricorsivo; Alla base di questo metodo c'e' il procedimento Divide et Impera, che consiste nella divisione di un problema in problemi via via piu' piccoli. Il merge sort opera quindi dividendo l'insieme da ordinare in 2 meta'. Una volta ottenute le meta' si provede alla loro fusione ordinandole.

Procedimento:

Il vettore viene diviso in due meta', se e' formato da un numero pari di elementi la prima parte ha un elemento in piu'. Si ordinano le parti separatamente e per unirle l'algoritmo estrae il minimo dalle due parti e li fonde in un'unica sequenza.

Esempio pratico:

Supponiamo di avere un array:

dividiamo l'array in 2 meta' e ripetiamo il processo ricorsivamente fino ad ottenere coppie di 2 elementi:

ordiniamo le coppie ottenute:

e fondiamo in un unico vettore estraendo dagli array ordinati:

L'intero procedimento e' il seguente:

Pseudocodice:

Pseudocodice per l'ordinamento di un vettore di n elementi

Se ci sono almeno 2 elementi da ordinare:

  1. dividi la sequenza in 2 meta';
  2. chiamata ricorsiva di mergesort per la prima meta';
  3. chiamata ricorsiva di mergesort per la seconda meta';
  4. fusione delle due meta'.

Codice:

#include <iostream.h>


void mergesort(int[], int, int);
void merge(int[], int, int, int);
 
main() 
{
  //numero di elementi nel vettore
  const int n = 8;
  //vettore da ordinare
  int a[n]={4, 6, 2, 7, 8, 9, 3, 1};
  int i;
  //chiamata alla funzione di ordinamento
  mergesort(a, 0, n-1);
  //visita del vettore
  for(i=0; i<n; i++)
  {
    cout <<a[i];
  }
}


void mergesort(int a[], int left, int right)
{
  //indice dell'enemento mediano
  int center;
  //se ci sono almeno di 2 elementi nel vettore
  if(left<right)
  {
     //divido il vettore in 2 parti
     center = (left+right)/2;
     //chiamo la funzione per la prima meta'
     mergesort(a, left, center);
    //chiamo la funzione di ordinamento per la seconda meta'
     mergesort(a, center+1, right);
    //chiamo la funzione per la fusione delle 2 meta' ordinate
     merge(a, left, center, right);
  }
}


void merge(int a[], int left, int center, int right) 
{
  int i, j, k;
  //vettore di appoggio 
  int b[8];
  i = left;
  j = center+1;
  k = 0;
  //fusione delle 2 meta'
  while ((i<=center) && (j<=right)) 
  {
    if (a[i] <= a[j]) 
    {
      b[k] = a[i];
      i++;
    } 
    else 
    {
      b[k] = a[j];
      j++;
    }
    k++;
  }
  
  //se i e' minore di center significa che alcuni elementi 
  //della prima meta' non sono stati inseriti nel vettore
  while (i<=center) 
  {
    //allora li aggiungo in coda al vettore
    b[k] = a[i]; 
    i++;
    k++;
  }
 
  //se j a' minore di right significa che alcuni elementi 
  //della seconda meta' non sono stati inseriti nel vettore
  while (j<=right) 
  {
    //allora li aggiungo in coda al vettore
    b[k] = a[j];
    j++; 
    k++;
  }
 
  //alla fine copio il vettore di appoggio b nel vettore a 
  for (k=left; k<=right; k++)
  {
    a[k] = b[k-left];
  }
}
Creative Commons License
Questo/a opera e' pubblicato sotto una Licenza Creative Commons.