Differenze

Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.

--- fisica:informatica:201617:esercitazione13 [05/05/2017 alle 13:25 (8 anni fa)] – creata Susanna Pelagatti
+++ fisica:informatica:201617:esercitazione13 [05/05/2017 alle 13:52 (8 anni fa)] (versione attuale) – [Esercizio 3: (avanzato) Usare il ''qsort()'' della libreria standard C] Susanna Pelagatti
@@ Linea 12: / Linea 12: @@
 ===== Esercizio 3: (avanzato) Usare il ''qsort()'' della libreria standard C =====
-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 tipo:
+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:
 <code>
+void qsort (void* buf, size_t num, size_t size, int (*compare) (const void*, const void*))
+</code>
+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:
+<code>
+int compare (const void * x, const void * y);
+</code>
+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:
+<code>
+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);
+.....
 </code>
+oppure per le stringhe
+<code>
+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);
+...
+</code>
+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.