Veremos agora um algoritmo de ordenacao que se propoe a ordenar um conjunto de numeros em tempo linear. Sabemos que este problema e O(n.log(n)), entao atacamos um problema um pouco menos generico, do qual temos algumas informacoes a priori: podemos supor que a quantidade de digitos dos numeros a serem ordenados e finito (de acordo com uma base) e conhecido.Eis o codigo:/*** MAC 2301 - Laboratorio de Programacao** Exercicio da aula 4** Ordenacao por distribuicao (aka radix sort)***/#include #include #define BASEMAX 10#define UNDERFLOW -1#define OVERFLOW -1typedef struct cel{ int chave; struct cel *prox;} celula;/* complexidade desta funcao: O(tamanho da fila) */void imprimeFila (celula *inicio){ celula *varre = inicio; printf("\n ordenando -> "); while (varre != NULL) { printf (" %d ", varre->chave); varre = varre->prox; } printf("\n\n");}/* complexidade desta funcao: O(1) = constante */int insereNaFila (int x, celula **inicio, celula **fim){ celula *nova; nova = malloc (sizeof (celula)); if(nova == NULL) return OVERFLOW; nova->chave = x; nova->prox = NULL; if((*fim) == NULL) *inicio = nova; else (*fim)->prox = nova; *fim = nova; return 0;}/* O(1) */int proximoDaFila (int *valorDevolvido, celula **inicio, celula **fim){ celula *morta; if(*inicio == NULL) return UNDERFLOW; morta = *inicio; *valorDevolvido = (*inicio)->chave; if(morta->prox == NULL) *fim = NULL; *inicio = morta->prox; free (morta); return 0;}/* O(tamanho da fila) */void removeFila(celula* fila){ celula* morta; while(fila != NULL) { morta = fila; fila = fila->prox; free(morta); }}/* funcoes auxiliares *//* O(1) */int max(int um, int outro){ if(um > outro) return um; return outro;}/* O(numero de digitos de umNumero) */int numDigitos(int umNumero){ int numDig = 1; while(umNumero > 0) { umNumero /= 10; numDig++; } return numDig;}/* O(i) */int iesimoDigitoMenosSignif(int numero, int i){ while(i > 1) { numero = numero / 10; i--; } return numero % 10;}int main(){ celula* inicioDaFilaASerOrdenada; celula* fimDaFilaASerOrdenada; celula* iniciosDasFilas[BASEMAX]; celula* finaisDasFilas[BASEMAX]; int quantDeNumeros, base, numDig; int i, j; /* contadores */ int k, temp; /* variaveis auxiliares */ inicioDaFilaASerOrdenada = NULL; fimDaFilaASerOrdenada = NULL; printf(" Base numerica? \n -> "); scanf("%d", &base); for(i = 0; i < base; i++) /* laco 1, executado 'base' vezes */ { iniciosDasFilas[i] = NULL; /* O(1) */ finaisDasFilas[i] = NULL; /* O(1) */ } printf(" Quantidade de numeros? \n -> "); scanf("%d", &quantDeNumeros); printf(" Digite os numeros a serem ordenados:\n"); /* Agora leremos os numeros a serem ordenados e, a cada numero, * inserimos esse numero na fila principal e contamos seu numero * de digitos para guardar o maior deles */ numDig = 0; for(i = 0; i < quantDeNumeros; i++) /* laco 2, executado 'quantDeNumeros' vezes */ { printf(" --> "); /* O(1) */ scanf("%d", &temp); /* O(1) */ insereNaFila(temp, &inicioDaFilaASerOrdenada, /* O(1) */ &fimDaFilaASerOrdenada); numDig = max(numDig, numDigitos(temp)); /* O(numero de digitos de temp) */ } /* o algoritmo consite basicamente em numDig iteracoes */ for(i = 1; i <= numDig; i++) /* laco 3, executado 'numDig' vezes */ { /* primeiro varremos a fila principal e distribuimos * seus elementos pelas outras filas, de acordo com * o i-esimo digito menos significativo */ for(j = 0; j < quantDeNumeros; j++) /* laco 3.1, executado 'quantDeNumeros'