jump to navigation

Generic quicksort 28 novembre 2007

Posted by fripp in Algoritmi, C, Informatica, Ordinamento, Programmazione, Quicksort.
Tags: , , ,
trackback

Nel post precedente ho parlato di come poter usar i void* in C come tipi generici da usare per render estremamente flessibile le funzioni e il codice in generale; ho parlato pure dellla funzione qsort della libreria standard del C che è l’esempio più concreto di come si possa fare uso dei void*.

In questo post scendo nei particolari del problema mettendo a vostra disposizione il codice di una mia implementazione generica del quicksort. Premetto che non mi soffermerò sull’algoritmo in se, visto che su internet ci sono abbondanti trattazioni al riguardo.

Ecco il blocco di codice:

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

//prototipi delle funzioni
typedef int (*compare_function)(const void*,const void*); 

void generic_quicksort(void *v, int i, int f, size_t size, compare_function compare);
void generic_swap(void *a, void *b, size_t size);
int generic_partition(void *v, int i, int f, size_t size, compare_function compare);

//funzione di confronto
int compare_int(const void*,const void*); 

int main(){
	int v[]={5,4,3,2,1};

	int n=sizeof(v)/sizeof(int);

	generic_quicksort((void*) v,0,n-1,sizeof(int),compare_int);

	return 0;
} 

int compare_int(const void *a, const void *b){
	return *((int*)a)-*((int*)b);
} 

void generic_quicksort(void *v, int i, int f, size_t size, compare_function compare){
    if(i>=f)
        return;

    int p=generic_partition(v,i,f,size,compare);

    generic_quicksort(v,i,p-1,size,compare);
    generic_quicksort(v,p+1,f,size,compare);

}

void generic_swap(void *a, void *b, size_t size){
    void *tmp=malloc(size);

    memcpy(tmp,a,size);
    memcpy(a,b,size);
    memcpy(b,tmp,size);

    free(tmp);
}

int generic_partition(void *v, int i, int f, size_t size, compare_function compare){
    void *x=malloc(size);

    memcpy(x,v+(i*size),size);

    int inf=i;
    int sup=f+1;

    while(1){
        do
            inf++;
        while(compare(v+(inf*size),x)< =0 && inf<=f);

        do
            sup--;
        while(compare(v+(sup*size),x)>0);

        if(inf<sup )
            generic_swap(v+(inf*size),v+(sup*size),size);

        else
            break;
    }

    generic_swap(v+(i*size),v+(sup*size),size);

    free(x);

    return sup;
}

&#91;/sourcecode&#93;

La funzione <em>generic_quicksort prende come argomento:
<ul>
	<li><em>un </em><em>void*</em> che puterà al vettore da ordinare;</li>
	<li><em>gli indici del primo e dell'ultimo elemento dell'array da ordinare;</em></li>
	<li><em>la dimensione </em><em>size</em> di ogni element dell'array;</li>
	<li><em>un </em><em>puntatore a funzione</em> che servirà per comparare gli elementi del vettore;</li>
</ul>
<em>I parametri </em><em>size</em> e<em> compare</em> sono fondamentali. Avendo a che fare con un tipo non definito, è necessario conoscer la dimensione in byte di ogni elemento dell'array per poter acceder ad ognuno di essi attrverso l'aritmetica dei puntatori; la funzione di comparazione è indispensabile sia perchè senza di essa non potremmo fare alcun confronto tra tipi generici, sia perchè rende ancor più flessibile il nostro algoritmo di ordinamento (l'uso di una funzione di comparazione ci permette di definire la relazione d'ordine tra gli elementi dell'array secondo le nostre esigenze).

<em>Le cose più interessanti si trovano nella funzione </em><em>generic_partition</em>, dove si vede chiaramente l'approccio "a basso livello" necessario per gestire la situazione. Dato che i <em>void*</em> non possono esser dereferenziati, l'unico modo per acceder agli elemnti del vettore è tramite il loro indirizzo. Nell'utilizzare l'aritmetica dei puntatori occore usare la dimensione del tipo di dato, passata come parametro alla funzione, per incrementare in maniera corretta il puntatore.

<em>Di solito, quando si usano i puntatori ai tipi definiti (int ,double....), l'incremento del puntatore di uno comporta uno spostamento in memoria di "sizeof(type)" bytes. Nel caso dei </em><em>void* </em>occorre specificare <em>"</em>manualmente" tale scostameto; un incremento di uno per un puntatore a void comporta uno spostamento in memoria di un solo byte.

<em>Altra cosa che occorre per la gestione a basso livello della memoria è l'uso delle funzioni della classe mem*, come la memcpy, che permettono di manipolare porzioni di byte semplicemente specificandone dimensione e indirizzo.</em>

<em>Il prototipo della memcpy è il seguente:</em>
<pre><em>

#include <string .h>

void memcpy(void *a, const void *b, size_t size);


Tale funzione copia “size” bytes puntati da b all’indirizzo puntato da a.L’implementazione di “funzioni generiche” in C necessita un controllo a basso livello della memoria da parte del programmatore; se da un lato questo può esser particolarmente stimolante (io mi diverto un casino!), dall’altro richiede molta attenzione (la segmentation fault è sempre dietro l’angolo se non si fanno gli opportuni controlli!).Enjoy……….

Annunci

Commenti»

1. Quickselect « frammenti di razionalità - 8 maggio 2008

[…] di partizionamento è uguale a quella implementata nel caso del quicksort generico presentato in questo […]

2. Tex - 13 maggio 2008

# do
# sup–;
# while(compare(v+(sup*size),x)>0);

do
sup–; // attenti è —
while(compare(v+(sup*size),x)>0);

ciao

3. Tex - 13 maggio 2008

wordpress fa vedere – – come un solo –

4. Tex - 13 maggio 2008

qua c’è il codice come compilatore uso dev-cpp non funziona

http://rafb.net/p/Q6jqX831.html

ciao

5. Calogero - 13 maggio 2008

Ho letto e compilato il tuo codice.
L’unico motivo per cui non funziona è che c’è una parentesi in più quando chiami la funzione generic_quicksort nel main.
Tu hai scritto
generic_quicksort((void*)z,0,n-1,sizeof(int),compare_int));

Dovresti scrivere
generic_quicksort((void*)z,0,n-1,sizeof(int),compare_int);
Per il resto funziona

6. Tex - 14 maggio 2008

eliminando la parentesi rimane:
riga 54 memcpy(x,v+(i*size),size);
pointer of type `void *’ used in arithmetic

e altri errori simili se usi dev-cpp che è basta sempre su gcc te ne accorgi

ciao

7. Tex - 14 maggio 2008

basta=basato

8. Calogero - 14 maggio 2008

Al più dovrebbe darti un warning, non un errore. Ho compilato il tuo codice con Mingw, che è il compilatore che sta sotto Dev-C++; Dev-C++ in se non è un compilatore, è (o cerca di esser) un IDE.
Mingw non mi da alcun errore o warning.
In genere il compilatore gcc è abbastanza “buono” e non è per nulla schizzinoso! Compila tutto, anche perchè il C ti permette di prenderti molte libertà che altri linguaggi non ti consentono.
Se è un warning e ti genera comunque l’eseguibile, non dare retta al compilatore!
Il codice è sicuramente giusto e funzionante

9. Tex - 14 maggio 2008

il mio codice che poi è il tuo soltanto che passo un vettore castato a void* z l’ho copiato e compilato ( aggiusta la funzione generic_quicksort alla quale non passi alcun puntatore dell’array )

ti linko il fatto che non ho warning ma non compila e basta

ciao 🙂

10. Tex - 14 maggio 2008

ho salvato il file con l’estensione .c anzichè .cpp scusate dell’errore ma adesso mi da errore qua http://img413.imageshack.us/img413/3743/snapyasnapshotfi2.jpg
ho aggiunto un meno al sup meno cambiandolo con sup meno meno
?!??!!??!?!

11. fripp - 14 maggio 2008

Fai una cosa: riscrivi sup– (come al solito WordPress non fa vedere i due meno) a mano. Il problema è di codifica dei caratteri.
L’ho avuto pure io

12. Tex - 15 maggio 2008

riscrivo sup con un solo meno ma non cambia nulla il compilatore si ferma sulla memcpy scusa ancora se non funziona …. t dovevo chiedere una cosa ma la tesi di laurea l’hai pubblicata su ieee? la si può leggere se si dove?

13. fripp - 16 maggio 2008

sup lo devi scrivere con due meno!!
Cambia compilatore, il codice è giustissimo!
Non ho pubblicato la tesi su ieee, è in formato ieee.
Come mai sei interessato a leggerla?

14. Tex - 16 maggio 2008

sup scritto con 2 meno vabè ho cpt il minigw non lo compila proverò con il gcc di linux….chiedevo per capire quale campo informatico hai trattato! Poi se non l’hai pubblicata avrai le tue ovvie ragioni!

15. fripp - 16 maggio 2008

La mia tesi di laurea tratta del problema della mancanza di un’architettura di rete unitaria per le reti di sensori wireless.
Se ti interessa, posso darti qualche riferimento bibliografico

16. Girolamo - 14 giugno 2008

in questo codice non si stampa il vettore in ambiente dev viene rilevato che i puntatori void non possono essere trattati in maniera aritmetica usa dev e vedrai che non funge

17. fripp - 15 giugno 2008

E tu non usare il Dev-C++! Non è il massimo per programmare. I puntatori a void li puoi usare in aritmetica come tutti gli altri………..vedi un manuale serio di C. L’unica cosa che non puoi fare è quello di dereferenziarli!
In quel caso qualsiasi compilatore si incazza come una bestia!

18. Nicola - 3 gennaio 2009

#include
#include
#include

typedef int (* compare_function) (void * , void *);

void generic_quicksort(void *a , int inizio , int fine , size_t size ,compare_function compara);
int partiziona(void *,int , int ,size_t,compare_function);
void scambia(void * , void * , size_t);
int compare( void *perno ,void *elemento);
void stampa(int [] , int);
int compare_stringhe(void * , void *);
void stampa_stringhe(char *[] , int);

int main()
{
int a[]={23,12,34,56,10};
int dim = sizeof(a)/sizeof(int);
generic_quicksort(a , 0 , dim-1 ,sizeof(int), compare);
stampa(a,dim);

char *b[]={“ape”,”zanzara”,”zebra”,”leone”,”tigre”,”ghepardo”,”leopardo”,”puma”,”gatto”,”lince”,”pantera”,”gattopardo”,”antilope”,”panda”};
dim=sizeof(b)/sizeof(char *);
generic_quicksort(b,0,dim-1,sizeof(char *),compare_stringhe);
stampa_stringhe(b,dim);
}

void generic_quicksort(void *a , int inizio , int fine , size_t size ,compare_function compara)
{
if(inizio>=fine)
return;

int perno = partiziona(a,inizio,fine,size,compara);
generic_quicksort(a , inizio , perno-1 , size , compara);
generic_quicksort(a , perno+1 , fine , size ,compara);
}

int compare_stringhe( void *perno , void *elemento)
{
/*Cerchiamo di capire quello che c’è scritto. Scrivendo void *perno intendo void (* perno) cioè perno è un puntatore a void e per definizione
non può essere deferenziato cioè non si può scrivere *perno. Un puntatore a void punta ad un’area di memoria indicata da noi ma non può accedere
al contenuto(cioè non può essere deferenziato).
Scrivendo [(int *) perno] significa che il puntatore a void perno viene convertito in un puntatore a interi. Una volta diventato un puntatore a
interi può essere deferenziato cioè si può scrivere [*((int *) perno)].
La stessa cosa vale per le stringhe. perno è un puntatore a void punta all’indirizzo di memoria che costituisce l’iniziale della parola;
(infatti l’array di puntatori iniziale contiene per ogni cella l’indirizzo della memoria contenente l’iniziale della parola).
quindi perno deve essere convertito in un puntatore che punta ad un’area di memoria che contenga a sua volta un puntatore a char.
Da qui deriva la scrittura (char * *)perno :perno è un puntatore a puntatore a char. A questo punto si può deferenziare perno per accedere
all’indirizzo di memoria scrivendo *((char **) perno).*/
return strcmp(*((char* *) elemento) , *((char* *) perno));
}

//compara interi
int compare( void *perno ,void *elemento)
{
return *((int *)elemento)-*((int *)perno);
}

int partiziona(void *a , int inizio , int fine , size_t size , compare_function compara)
{
void *perno=a+inizio*size; //quando incremento di 1 un puntatore a void si incrementa l’indirizzo di 1 byte.
int inf=inizio;
int sup=fine+1;

while(1)
{
do
{
++inf;
}while(inf<=fine && compara(perno,a+inf*size)0);

if(inf<sup)
scambia(a+inf*size , a+sup*size , size);
else
break;
}

scambia(perno,a+sup*size , size);
return sup;
}

void scambia(void *a , void *b , size_t size)
{
void *temp=malloc(size);

memcpy(temp,a,size);
memcpy(a,b,size);
memcpy(b,temp,size);

free(temp);
}

void stampa(int a[] , int dim)
{
int i;
printf(“\nL’array ordinato è:\n\n”);
for(i=0 ; i<dim ; i++)
printf(“%-7d”,a[i]);
printf(“\n\n\n”);
}

void stampa_stringhe(char * a[] , int dim)
{
int i;
printf(“\nL’array di stringhe ordinato è:\n\n”);
for(i=0 ; i<dim ; i++)
printf(“%-10s”,a[i]);
printf(“\n\n\n”);
}

Il codice all’inizio del sito presenta un errore.
Nella chiamata a generic_sort dal main si deve passare l’array v e non (void *). Il mio codice presenta delle personalizzazioni e l’ordinamento generico di stringhe rispetto a quello precedente.

19. Nicola - 3 gennaio 2009

I package della libreria standard da includere sono gli stessi di prima. Non so perchè ma non sono stati visualizzati insieme al codice


Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: