libri-javascript-python

Oggi tratteremo il merge sort in C.

Il merge sort è un algoritmo di ordinamento inventato da Von Neumann nel 1945.

È un algoritmo di ordinamento più complesso ma molto più efficiente degli altri visti in precedenza (selection sort e insertion sort), soprattutto con vettori di grandi dimensioni.

Sfrutta la tecnica divide et impera, ovvero la suddivisione del problema in sotto-problemi della stessa natura di dimensione a mano a mano sempre più piccola, li risolve ricorsivamente e infine combina le soluzioni parziali per ottenere la soluzione al problema di partenza.

Quindi si divide ricorsivamente il vettore in due parti da ordinare separatamente. Successivamente si fondono le due parti per ottenere un array ordinato globalmente.

Il merge sort utilizza inoltre un array di appoggio.

Implementazione del merge sort in C

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

#define max 100

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);
}

void stampa_array(int V[], int n) {
  int i;
  for (i=0; i<n; i++) {
    printf("%d ", V[i]);
  }
  printf("\n");
  return;
}

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;
}

void mergeSort(int a[], int p, int r) {
  int q;
  if (p < r) {
    q = (p+r)/2;
    mergeSort(a, p, q);
    mergeSort(a, q+1, r);
    merge(a, p, q, r);
  }
  return;
}

int main(void) {
  int n, V[max];
  n = insert_array(V);
  mergeSort(V, 0, n-1);
  stampa_array(V, n);
  return(0);
}

Prestazioni

L’algoritmo sia nel caso medio che in quello pessimo ha una complessità pari  a Θ (n log n). La complessità della funzione merge é lineare Θ(n).

Alcuni link utili:

Array o vettori

Selection sort in linguaggio C

Quick sort in linguaggio C

Insertion Sort in linguaggio C