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

#include

#include

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;iqui 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.

Annunci

Commenti»

No comments yet — be the first.

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: