Sortare radix folosind cozi

Se foloseste urmatoarea interfata pentru tipul de date Coada:

queue.h

#ifndef _QUEUE_H

#define _QUEUE_H

typedef struct nod{

void* data;

struct nod* next;

}q_nod;

typedef q_nod* Queue;

/* adaugare in coada */

int enqueue(Queue*, void*);

/* extragere din coada */

void* dequeue(Queue*);

/* inspectarea primului element */

void* Front(Queue);

/* test coada vida */

int isEmpty(Queue);

/* dimensiunea cozii */

int size(Queue);

#endif

queue.c

#include "stdlib.h"

#include "queue.h"

int enqueue (Queue *Q,void *x){

Queue aux,pus;

aux = *Q;

if (aux!=NULL){

while (aux->next!=NULL)

aux = aux->next;

pus = (Queue)malloc(sizeof(q_nod));

pus->data = x;

aux->next = pus;

pus->next = NULL;

return 0; }

else {

aux = (Queue)malloc(sizeof(q_nod));

aux->data = x;

aux->next = NULL;

*Q = aux;

return 0;

}

}

void* dequeue (Queue *Q){

Queue aux;

aux = *Q;

if(*Q==NULL) return NULL;

void* x = (*Q)->data;

*Q = (*Q)->next;

free(aux);

return x;

}

void* Front (Queue Q){

if (Q==NULL)

return NULL;

else

return Q->data;

}

int isEmpty (Queue Q){

return Q==NULL;

}

int size (Queue Q){

int k = 0;

Queue aux = (Queue)malloc(sizeof(q_nod));

aux = Q;

while (aux!=NULL){

k++;

aux = aux->next;

}

return k;

}

Sortarea este urmatoarea:

#include "queue.h"

#include "stdio.h"

#include "stdlib.h"

#include "math.h"

int rangmax (int n, int *X){

int xm = X[0];

int k, r;

for (k=0; k

if(X[k] > xm)

xm = X[k];

r = 0;

while (xm > 0){

r++;

xm/=10;

}

return r;

}

void Distribuie (int n, int* X, Queue* QC, int r){

int nc=0, ind, i, j, *pi;

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

int t=X[i];

for(j=0; j <=r-1; j++)

t /= 10;

ind = t % 10;

if(isEmpty(QC[ind]))

nc++;

pi = (int*)malloc(sizeof(int));

*pi = X[i];

enqueue(&QC[ind], pi);

}

}

void Colecteaza (Queue* QC, int* X){

int j, i=0, *pi;

for (j=0; j<=9; j++)

while(!isEmpty(QC[j])){

pi = dequeue(&QC[j]);

X[i] = *pi;

i++;

free(pi);

}

}

void RadixSort (int n, int* X){

int rmx, i, r;

Queue QC[10];

for(i=0; i<=9 ; i++)

QC[i]= NULL;

rmx = rangmax(n, X);

for (r=0; r<=rmx; r++){

Distribuie(n, X, QC, r);

Colecteaza(QC, X);

}

}

int main(){

int n, i;

int *x;

scanf("%d", &n);

x = (int*)malloc(n*sizeof(int));

for(i=0; i<=n-1; i++)

scanf("%d", &x[i]);

RadixSort(n, x);

for(i=0; i<=n-1 ; i++)

printf("%5d ", x[i]);

printf("\n");

free(x);

return 0;

}