LabASD - Merge sort

Implementare l’algoritmo Merge sort in modo tale che i test forniti nello schema di programma allegato vengano superati. Merge sort è stato ideato da John Von Neumann nel 1945.

L’algoritmo Merge Sort basa il suo funzionamento sul paradigma divide et impera. L’array da ordinare viene diviso in due metà che sono ordinate ricorsivamente. Le metà ordinate vengono ricomposte mediante una procedura merge(). Si faccia riferimento alla Figura 1 per un esempio.

Nell’algoritmo Merge Sort la fase divide è semplice, mentre la fase impera (fusione di due array ordinati) è più laboriosa da realizzare. Si faccia riferimento al materiale fornito nella parte di teoria per i dettagli.

Chiamiamo \(T(n)\) il tempo necessario ad ordinare un array di lunghezza \(n\) usando Merge Sort; possiamo definire \(T(n)\) in modo ricorsivo come segue:

\[ T(n) = \begin{cases} c_1 & \mbox{se } n \leq 1 \\ 2T(n/2) + c_2 n & \mbox{altrimenti} \end{cases} \]

dove \(c_1\) e \(c_2\) sono costanti. La componente \(c_2 n\) indica il tempo necessario alla fase di fusione (merge), che è proporzionale alla somma delle lunghezze delle metà da fondere. Risolvendo la ricorrenza, ad esempio usando il Master Theorem, si ha \(T(n) = \Theta(n \log n)\).

L’algoritmo Merge Sort può essere realizzato in modo ricorsivo o iterativo; in questo esercizio verrà proposta la soluzione ricorsiva, ma chi lo desidera può implementare l’altra.

Il programma fornito contiene alcuni test per verificare la parziale correttezza della funzione merge_sort(). Nei test si confronta il risultato prodotto da merge_sort() con quello della funzione qsort() della libreria standard C. La dichiarazione di qsort() è:

#include <stdlib.h>

void qsort(void *base, size_t nmemb, size_t size,
           int (*compare)(const void *, const void *));

dove:

• base è un puntatore all’inizio dell’array da ordinare;

• nmemb è il numero di elementi dell’array da ordinare (attenzione, non il numero di byte!)

• size è la dimensione in byte di ciascuno degli elementi dell’array

• compare è un puntatore ad una funzione int cmp(const void *a, const void *b) (il nome della funzione e dei parametri possono essere scelti in modo arbitrario) che restituisce:

  • un valore negativo, se *a viene prima di *b nell’ordinamento;

  • zero, se *a e *b sono considerati uguali;

  • un valore positivo, se *a viene dopo *b nell’ordinamento

Compilare con:

    gcc -std=c90 -Wall -Wpedantic merge-sort.c -o merge-sort

Per eseguire in ambiente Linux/MacOSX:

    ./merge-sort

Per eseguire in ambiente Windows:

    .\merge-sort

Uso della funzione qsort()

Riportiamo un esempio di come usare la funzione qsort() per ordinare un array di interi (è possibile ordinare un array di tipo qualunque).

Occorre innanzitutto definire una funzione usata per confrontare gli elementi da ordinare, che qui chiamiamo cmp_increasing(). Il nome della funzione è arbitrario, ma il tipo dei parametri e del risultato devono essere conformi a quanto sopra, cioè deve accettare due parametri di tipo const void* e restituire un intero. La funzione deve conoscere il vero tipo degli elementi dell’array da ordinare, per cui bisogna definire una funzione diversa per ogni tipo di dato da ordinare. Nel nostro caso, i puntatori a e b vanno convertiti a puntatori a interi costanti, per poi essere internamente dereferenziati per confrontare il valore puntato.

Il programma seguente mostra come si possa utilizzare in pratica la funzione qsort().

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

int cmp_increasing(const void *a, const void *b)
{
  const int va = *(const int*)a;
  const int vb = *(const int*)b;
  if (va < vb)
    return -1;
  else if (va > vb)
    return 1;
  else
   return 0;
}

int main( void )
{
  int a[] = {13, 0, -3, 4, 2};
  int i;
  const int LEN = sizeof(a)/sizeof(a[0]);

  qsort(a, LEN, sizeof(int), cmp_increasing);
  for (i=0; i<LEN; i++) {
    printf("%d ", a[i]);
  }
  printf("\n");
  return 0;
}

Internamente alla funzione cmp_increasing() occorre convertire i parametri da “puntatore ad un valore generico costante” a “puntatore a intero costante”, per poi dereferenziarlo per leggere il valore puntato. Conviene ragionare per passi:

• a ha tipo “puntatore ad un valore generico costante”;

• (const int *)a ha tipo “puntatore ad un valore intero costante”;

• *(const int *)a ha tipo “intero costante”

L’uso della parola chiave const è importante: l’espressione (int *)a produce (come minimo) un warning, perché ha come valore un puntatore non costante. Questo violerebbe il vincolo originale che richiede che il valore puntato da a non possa essere modificato.

Suggerimenti

La funzione merge() richiede un buffer temporaneo per effettuare la fusione dei sottovettori ordinati. È possibile allocare e deallocare il buffer all’interno di merge() ad ogni chiamata, ma ciò sarebbe inefficiente. Nel codice fornito, la funzione sort() alloca un buffer di lunghezza \(n\) e lo passa alle funzioni merge_sort() e merge(). Solo merge() utilizza il buffer, eliminando l’overhead che sarebbe causato dalle ripetute chiamate a malloc() e free().

Per approfondire

Questo programma misura in modo grossolano il tempo necessario a ordinare l’array. Considerando array di dimensioni sufficientemente grandi (es., 100000 elementi o più), come varia (se varia…) il tempo di esecuzione nei seguenti casi? Le risposte dovrebbero essere note dalla teoria.

• Input già ordinato.

• Input “quasi” ordinato (esempio, array ottenuto da un array ordinato in cui si scambiano tra loro due elementi in posizioni casuali \(i\), \(j\)).

• Input ordinato in senso decrescente.

• Input casuale.

• Input composto da tutti valori uguali.

Per eseguire le misure occorre modificare la funzione main() per generare degli input opportuni. Nel caso possano risultare utili, vengono fornite due funzioni randab() e random_shuffle(), la cui specifica è indicata nei commenti al codice.

File

• merge-sort.c