Implementare una funzione ordinaBin che ordina un array di valori binari (0/1) mettendo prima tutti i valori uguali a 0 e poi tutti qulli uguali ad 1. E' possibile realizzare la funzione ispezionando ogni elemento dell'array una sola volta. Come ?

Scrivere tre funzioni che implementano gli algoritmi di ordinamento visti a lezione su array di double.

Valutare i tempi di esecuzione su array di double lunghezza crescente generati casualmente nell'intervallo [0,1](usare il comando time). Ci sono delle variazioni ?

Cercare una formula (approssimata) che fornisca il numero di istruzioni eseguite dai tre algoritmi di ordinamento in funzione di n, lunghezza dell'array da ordinare.

La libreria standard C mette a disposizione una implementazione dell'algoritmo quicksort “generica” ovvero che può essere utilizzata con array di elementi di uno qualsiasi dei tipi base C. La funzione ha il seguente prototipo:

void qsort (void* buf, size_t num, size_t size, int (*compare) (const void*, const void*))

dove buf è il puntatore al primo elemento dell'array da ordinare, num è il numero di elementi dell'array, size è la lunghezza in byte di ogni elemento e compare è un puntatore a (nome di) una funzione che fa il confronto fra due elementi dell'array, ovvero l'indirizzo della prima istruzione della funzione (area text). Una funzione compare utilizzabile a questo scopo deve avere tipo:

int compare (const void * x, const void * y); 

e deve confrontare *x e *y in modo da restituire un valore

• negativo → se *x < *y
• 0 → se *x == *y
• positivo → se *x > *y

La parola chiave const significa che la funzione al suo interno non deve modificare mai le variabili puntate da x ed y. Inoltre è necessario inserire dei casti all'interno della funzione per specificare il tipo del puntatore prima di poterlo dereferenziare.

Ad esempio se sto lavorando con valori interi posso definire la funzione di confronto come:

int confronta_int (const void* x, const void* y) {
   int a = * (int *) x;
   int b = * (int *) y;
   return a-b;
}

#define N 6
int main(void){
int values[N] = {10, 21, 1 , 7 , 24 , 9};
qsort(values, N, sizeof(int), confronta_int);
.....

oppure per le stringhe

int confronta_string (const void* x, const void* y) {
   char* a = * (char* *) x;
   char* b = * (char* *) y;
   return strcmp(a,b);
}

#define N 10
int main(void){
int i;

char ** values = malloc(N*sizeof(char *));

for(i=0; i < n; i++) {
   values[i] = malloc((N+1)*sizeof(char));
   scanf(“%s”, values[i]);
}

qsort(values, N, sizeof(char *), confronta_string);
...

Utilizzare il qsort() della libreria standard per ordinare un array di interi, uno di double, uno di caratteri ed uno di strighe lunghe al massimo 40 caratteri.

Confrontare i tempi ottenti con quelli ottenuti le funzioni implementate nell'esercizio 2.