Regole per la preparazione dei progetti.

Ogni progetto può essere svolto da uno o due studenti. Questo consiste nel produrre  un codice  in C secondo la traccia data e di realizzare delle prove di esecuzione significative ai fini del progetto.
Dovrà poi essere consegnato un dischetto o un cd contenente il codice C unitamente al  corrispondente file già compilato ed una relazione stampata   in cui si descrivono brevemente le scelte implementative e le prove di esecuzioni del programma effettuate e si espongono brevemente osservazioni/commenti/conclusioni relative a tali prove.

I criteri di valutazione dei progetti comprendono: chiarezza, eleganza ed efficienza del codice C. Numero e significatività delle prove di esecuzione. Chiara esposizione di osservazioni e conclusioni sulla implementazione e sui risultati ottenuti  dall'esecuzione  su input diversi per dimensioni e proprietà.

• SESSIONE DI FEBBRAIO
  Progetto (da consegnare PERSONALMENTE) il 13 febbraio 2004 ore 10:00 presso lo studio del docente..)
  All'atto della consegna si richiede una breve discussione del progetto.

Leggere attentamente le "regole per la preparazione del progetto" sopra descritte.
Implementare un programma per testare e confrontare  i seguenti algoritmi di ordinamento:  selection sort,  bubble sort, insertion sort, merge sort e heap sort. Per ognuno di questi algoritmi scegliere una implementazione che ne evidenzi bene le qualità/caratteristiche.

Per ogni algoritmo si deve calcolare il  numero di confronti che questo esegue tra le chiavi (cioè tra gli elementi del vettore in input) e il numero di totale di operazioni  in cui sono "coinvolti" i valori delle chiavi (sia le operazioni di confronto che le operazioni di assegnamento).
Tutti gli  algoritmi andranno eseguiti sulle seguenti  diverse tipologie  di input:

• array permutazione ordinata
• array permutazione ordinata al contrario
• array permutazione quasi ordinata (vedi sotto)
• array permutazione quasi ordinata al controrio (vedi sotto)
• array permutazione random (vedi sotto)

Le permutazioni dovranno  essere ottenuto scambiando un certo numero di coppie di elementi a partire da  un vettore ordinato che contiene tutti gli elementi distinti. Ad esempio: sia A[ ] un vettore ordinato di dimensione N (es. N=100) che contiene i numeri da 1 ad N.  Una permutazione quasi ordinata si puo' ottenere spostando il 5% degli elementi scelti con la funzione rand (es. scambiando 5 coppie di elementi).  Una permutazione quasi ordinata al contrario si puo' ottenere similmente, partendo  da una permutazione ordinata al contrario.  Una permutazione random si puo' ottenere effenttuando 2N   spostamenti (es 200 scambi di coppie). Variando a piacere il numero di coppie random scambiate si possono ottenere svariate tipologie di input: per una permutazione random si puo' ad esempio scegliere di scambiare  4N coppie, o anche 10N,..... .

 L'output di tale programma dovrà presentare in forma di tabella (una per ogni algoritmo)   il numero di confronti  e il  numero di operazioni totali sulle chiavi  effettuati  dall'algoritmo stesso sulle varie tipologie di input a  parità di dimensione di array. Scegliere almeno due diverse dimensioni di array (una "piccola" ed una "grande"). Dovranno poi essere presentate delle tabelle di raffronto tra algoritmi diversi sulle tipologie di array "permutazioni" sopra descritte. In particolare si chiede un confronto diretto (cioè sullo stesso array) tra gli algoritmi selection sort,  bubble sort, insertion sort,  e tra insertion sort, merge sort e heap sort. Ancora una volta tale confronto va effettuato per almeno due dimensioni di vettore.

Commentare i risultati ottenuti evidenziando le qualita'/difetti di ogni algoritmo.

FACOLTATIVO:

1. fissata la tipologia del vettore permutazione e fissata la taglia, calcolare il numero di confronti su una media di almeno 20 vettori di quel tipo.
2. Effettuare i confronti tra gli algoritmi su diverse dimensioni del vettore (es. partire da dim=5 e poi incrementare di 5 in 5, cioè 5, 10, 15, 20,....1000 e poi partire da 500 e incrementare di 500 in 500, cioe' 500, 1000, 1500, .... 5000).