Merge sort in C, algoritmo di ordinamento merge sort in C

In questa lezione implementeremo l’algoritmo merge sort in C, un algoritmo di ordinamento che sfrutta la tecnica “divide et impera” per ottenere una soluzione efficiente. Ideato da John von Neumann nel 1945, il merge sort è noto per la sua efficacia con grandi insiemi di dati, avendo una complessità temporale pari a Θ(n log n) sia nel caso medio che nel caso peggiore.

L’approccio del merge sort consiste nei seguenti passaggi:

Divisione: Inizia dividendo ricorsivamente il vettore in due parti di dimensioni approssimativamente uguali finché ogni sotto-vettore contiene un solo elemento, considerato già ordinato.
Fusione: Successivamente, unisce (merge) i sotto-vettori ordinati in sottovettori più grandi mantenendo l’ordinamento. Questo processo di fusione continua finché non si ottiene un unico vettore ordinato contenente tutti gli elementi.

L’algoritmo merge sort utilizza un array ausiliario per eseguire la fusione dei sotto-vettori ordinati. Questo array è fondamentale per garantire che i dati siano combinati correttamente e mantenendo l’ordinamento.

Considerazioni sul merge sort in C

Inoltre è importante comprendere ulteriori aspetti e considerazioni sull’algoritmo merge sort.

Stabilità: Il merge sort è un algoritmo stabile, il che significa che preserva l’ordine relativo degli elementi con valori uguali. Questo può essere importante in alcune applicazioni in cui l’ordine originale degli elementi con valori identici deve essere mantenuto.
Parallelizzazione: Il merge sort è facilmente parallelizzabile. Poiché le operazioni di suddivisione e fusione possono essere eseguite indipendentemente su sottoinsiemi del vettore, è possibile sfruttare i vantaggi dell’elaborazione parallela per migliorare ulteriormente le prestazioni, soprattutto con insiemi di dati molto grandi.
Strutture dati collegate: Se si utilizzano strutture dati collegate invece di array, il merge sort può ancora essere applicato con successo. In questo caso, la fusione delle due liste collegate richiede una logica leggermente diversa rispetto alla fusione di array, ma il concetto di base rimane lo stesso.
Varianti del merge sort: Esistono diverse varianti del merge sort che possono adattarsi a esigenze specifiche. Ad esempio, il “bottom-up merge sort” evita la ricorsione e implementa l’algoritmo in modo iterativo. Questa variante può essere più efficiente in alcuni casi, soprattutto in contesti in cui la ricorsione è costosa in termini di memoria o prestazioni.
Utilizzo pratico: Il merge sort viene utilizzato ampiamente in molte applicazioni del mondo reale, come l’ordinamento di dati nei database, la gestione di file ordinati e la produzione di elenchi di classifica. La sua affidabilità, stabilità e complessità garantita lo rendono una scelta popolare in contesti in cui l’ordinamento efficiente è cruciale.

Programma che implementa il merge sort in c

Ecco di seguito una possibile implementazione del merge sort in C:

#include <stdlib.h>
#include <stdio.h>

#define max 100

// Funzione per l'inserimento degli elementi nell'array
int insert_array(int V[]) {
  int n, i;
  printf("Quanti elementi?: ");
  scanf("%d", &n);

  for (i=0; i<n; i++) {
     printf("elemento %d: ", i);
     scanf("%d", &V[i]);
  }
  return(n);
}

// Funzione per stampare l'array
void stampa_array(int V[], int n) {
  int i;
  for (i=0; i<n; i++) {
    printf("%d ", V[i]);
  }
  printf("\n");
  return;
}

// Funzione per fondere due sotto-vettori ordinati in un unico vettore ordinato
void merge(int a[], int p, int q, int r) {
  int i, j, k=0, b[max];
  i = p;
  j = q+1;

  while (i<=q && j<=r) {
    if (a[i]<a[j]) {
      b[k] = a[i];
      i++;
    } else {
      b[k] = a[j];
      j++;
    }
    k++;
  }
  while (i <= q) {
    b[k] = a[i];
    i++;
    k++;
  }
  while (j <= r) {
    b[k] = a[j];
    j++;
    k++;
  }
  for (k=p; k<=r; k++)
    a[k] = b[k-p];
  return;
}

// Funzione principale per eseguire il merge sort
void mergeSort(int a[], int p, int r) {
  int q;
  if (p < r) {
    q = (p+r)/2;
    mergeSort(a, p, q);    // Ordina il sotto-vettore sinistro
    mergeSort(a, q+1, r);  // Ordina il sotto-vettore destro
    merge(a, p, q, r);     // Unisci i sotto-vettori ordinati
  }
  return;
}

int main(void) {
  int n, V[max];
  n = insert_array(V);   // Inserimento degli elementi nell'array
  mergeSort(V, 0, n-1);  // Chiamata alla funzione merge sort
  printf("Array ordinato: ");
  stampa_array(V, n);    // Stampa dell'array ordinato
  return(0);
}

Per lo sviluppo dell’algoritmo ho sviluppato alcune funzioni:

Funzione insert_array: Questa funzione viene utilizzata per inserire gli elementi nell’array. Chiede all’utente quanti elementi inserire e poi itera attraverso l’array per inserire i valori.
stampa_array: Questa funzione stampa gli elementi dell’array. Prende come argomenti l’array V e la dimensione n, e quindi stampa gli elementi uno per uno.
Funzione merge: Questa funzione esegue la fusione di due sotto-vettori ordinati in un unico vettore ordinato. Prende come argomenti l’array a[] e tre indici p, q e r, che indicano rispettivamente l’inizio, il punto di mezzo e la fine dei sotto-vettori da unire.
Funzione mergeSort: Questa è la funzione principale che implementa l’algoritmo merge sort. Prende come argomenti l’array a[] e due indici p e r, che indicano rispettivamente l’inizio e la fine dell’array da ordinare. Questa funzione utilizza la ricorsione per dividere ricorsivamente l’array in sotto-vettori più piccoli, ordinandoli separatamente e poi unendoli utilizzando la funzione merge.
main: La funzione main è il punto di ingresso del programma. Qui vengono dichiarate le variabili necessarie, chiamata la funzione insert_array per inserire gli elementi nell’array, chiamata la funzione mergeSort per ordinare l’array e infine stampato l’array ordinato utilizzando la funzione stampa_array.

Prestazioni del merge sort

La complessità garantita del merge sort, Θ(n log n), lo rende uno degli algoritmi di ordinamento più efficienti e affidabili, specialmente con grandi insiemi di dati. La complessità della funzione merge è lineare, con una complessità temporale Θ(n).

In conclusione, il merge sort è una potente tecnica di ordinamento che offre prestazioni garantite e affidabili per la gestione di grandi quantità di dati. La sua implementazione richiede una comprensione dei concetti di divisione, fusione e ricorsione, ma una volta compreso, può essere applicato con successo a una vasta gamma di problemi di ordinamento.

Conclusioni

In questa lezione ho sviluppato il merge sort è un algoritmo di ordinamento potente, stabile ed efficiente, che offre prestazioni garantite e affidabili anche con grandi insiemi di dati. La sua applicabilità in una vasta gamma di contesti lo rende uno strumento fondamentale nell’arsenale di ogni programmatore.