Vai al contenuto

Primario: Sky Slate Blackcurrant Watermelon Strawberry Orange Banana Apple Emerald Chocolate Marble
Secondario: Sky Slate Blackcurrant Watermelon Strawberry Orange Banana Apple Emerald Chocolate Marble
Sfondo: Blank Waves Squares Notes Sharp Wood Rockface Leather Honey Vertical Triangles
Corsi di Laurea










ROX @ Unisa - Forum degli studenti di Ingegneria utilizza i cookie. Se prosegui la navigazione accetti il loro uso.    Accetto l'uso dei cookie
-->
Foto

[C] radix_sort


  • Effettua l'accesso per rispondere
Nessuna risposta in questa discussione

#1
Blackjack

Blackjack

    Moderatore globale

  • Moderatore
  • 2542 Messaggi:
Versione su interi:

[codice-c:2k5zuwcy]void radixsort_int(int *v, int size, int max)
{
int *a, *temp; //puntatori a matrici di interi di appoggio
int b = 16; //base su cui fare la suddivisione in cifre (decimali = 10, esadecimali = 16)
int d = 0; //numero di cifre (esadecimali) da usare per rappresentare i numeri
int i, j; //indici
int esp; //variabile d'appoggio per l'elevamento a potenza

while(max > 0)
{
d++;
max = max >> 4; //4 = log2(B)
}
a = malloc(sizeof(int)*size*d);

for (i = 0; i < size; i++)
{
a[i*d+d-1] = v[i]%b;
//printf("%d\t",a[i*d+d-1]);
for (j = d-2; j >= 0; j--)
{
esp = (pow(b,d-j));
a[i*d+j] = v[i]%esp;
a[i*d+j] = a[i*d+j]/(pow(b,d-j-1));
//printf("%d\t",a[i*d+j]);
}
// printf("\n");
}

for (j = d-1; j >= 0; j--)
{
temp = countingsort_by_column(a,size,d,j,B);
free(a);
a = temp;
}

for (i = 0; i < size; i++)
{
v[i] = 0;
for (j = 0; j < d; j++)
{
v[i] = v[i] + a[i*d+j]*pow(b,d-j-1);
}
}

free(a);
}

int* countingsort_by_column(int *a, int M, int N, int j, int k)
{
int *b, *c;
int i, l;

b = malloc(sizeof(int)*M*N);
c = malloc(sizeof(int)*k);

//inizializzazione counting vector
for (i = 0; i < k; i++)
{
c[i] = 0;
}

//conteggi nel counting vector
for (i = 0; i < M; i++)
{
c[a[i*N+j]] = c[a[i*N+j]]+1;
}

//passaggio a counting vector integrale
for (i = 1; i < k; i++)
{
c[i] = c[i]+c[i-1];
}

//copia dei valori in forma ordinata da una matrice all'altra
for (i = M-1; i >= 0; i--)
{
for (l = 0; l < N; l++)
{
b[(c[a[i*N+j]]-1)*N+l] = a[i*N+l];
//b[i*N+l] = a[i*N+l];
}
c[a[i*N+j]] = c[a[i*N+j]]-1;
}

free©;
return b;
}[/codice-c]


Immagine inviata
Immagine inviata
Immagine inviata

"L'amore è la capacità di avvertire il simile nel dissimile"




Leggono questa discussione 0 utenti

0 utenti, 0 ospiti, 0 utenti anonimi