jump to navigation

Radix sort 5 Febbraio 2008

Posted by fripp in Algoritmi, C, GNU/Linux, Informatica, Ordinamento, Programmazione, Radix sort, Unix.
Tags: , , , ,
trackback

Il radix sort è un algoritmo di ordinamento che permette di ordinare un insieme di n record con chiavi intere comprese tra 1 e k con un costo computazionale pari a O(n(1+\frac{\log k}{\log n})).

L’algoritmo utilizza un altro algoritmo di ordinamento per chiavi intere, chiamato Bucketsort; in particolare, il Radix sort effettua un numero di chiamata di Bucketsort pari al numero di cifre in cui si può esprimere la chiave più grande della collezione in una data base. Il radix ordina le chiavi a partire dalla loro cifra meno significativa.

Il costo di esecuzione O(n(1+\frac{\log k}{\log n})) si riferisce al caso in cui la base b=O(n).

Per maggiori informazioni sull’algoritmo, cliccate qui.

Ecco l’implementazione in C dell’algoritmo. Il codice in questione si limita ad ordinare un array di interi, ma è possibile estenderlo in modo da ordinare un qualsiasi array di record con chiavi intere.

Nell’implementazione si è fatto utilizzo della struttura dati GQueue, una lista doppiamente linkata messa a disposizione dalla libreria Glib:


#include <math.h>

#include <glib/gqueue.h>

#include <stdlib.h>

inline void new_bucketsort(int *v, int n, int cifra, int base){

    GQueue **y=calloc(base,sizeof(GQueue*));

    register int i;
    register int j=0;

    for(i=0;i<n;i++){

        int c=((int)floor(v[i]/pow(base,cifra)))%base;

        if(!y[c]){
            y[c]=g_queue_new();
            g_queue_push_tail(y[c],(gpointer)v[i]);

        }else{
            g_queue_push_tail(y[c],(gpointer)v[i]);
        }
    }

    for(i=0;i<base;i++)
        if(y[i])
            while(!g_queue_is_empty(y[i]))
                v[j++]=(int)g_queue_pop_head(y[i]);

    for(i=0;i<base;i++)
        if(y[i])
            g_queue_free(y[i]);

    free(y);
}

inline void radix(int *v, int dim, int k, int base){
    int numero_iterazioni =((int)(log(k)/log(base)))+1;

    register int i;

    for(i=0;i<numero_iterazioni;i++)
        new_bucketsort(v,dim,i,base);

}

Cliccando qui potrete trovare l’archivio 7z contentente i sorgenti e il makefile.Dimenticavo……..nel makefile richiamo l’utility pkg-config per impostare correttamente i flag di compilazione per la Glib.

Vi sonsiglio caldamente di installarla se non l’avete già fatto.

Commenti»

No comments yet — be the first.