Radix Ordenacion

Sitio WEB Recomendado

Estructura de Datos click here

1. include <stdio.h>
2. include <iostream.h>
3. include <conio.h>
4. include <math.h>
5. include <stdlib.h>
6. define MAX 20

void radixsort(int x[], int n) {

  int front[10], rear[10];
  struct {
    int info;
    int next;
  } node[MAX];
  int exp, first, i, j, k, p, q, y;
    for (i = 0; i < n-1; i++) {
    node[i].info = x[i];
    node[i].next = i+1;
  }
  node[n-1].info = x[n-1];
  node[n-1].next = −1;
  first = 0;
  for (k = 1; k < 5; k++) {
       for (i = 0; i < 10; i++) {
      rear[i] = −1;
      front[i] = −1;
    }

    while (first != −1) {
      p = first;
      first = node[first].next;
      y = node[p].info;
     exp = pow(10, k-1);
       j = (y/exp) % 10;
       q = rear[j];
      if (q == −1)
	front[j] = p;
      else
	node[q].next = p;
      rear[j] = p;
    }

    for (j = 0; j < 10 && front[j] == −1; j++);
      ;
    first = front[j];
 while (j <= 9) {
    for (i = j+1; i < 10 && front[i] == −1; i++);
	;
      if (i <= 9)
      {
	p = i;
	node[rear[j]].next = front[i];
      }
      j = i;
    }
    node[rear[p]].next = −1;
  }


  for (i = 0; i < n; i++) {
    x[i] = node[first].info;
    first = node[first].next;
  }

}

int main(void) { clrscr();

  int x[50] = {NULL}, i;
  static int n;
  int Veces;
  cout<<”******ORDENACION POR RADIX******\n”;
  printf(“\n\nNUMEROS A ORDENAR : “);
  cin>>Veces;
  cout<<”\nIngresa las “<<Veces<<” claves.\n\n”;
  for (n = 0;n<Veces; n++)
   if (!scanf(“  %d”,&x[n])) break;
  if (n)
    radixsort (x, n);
    cout<<”\n”;
    cout<<”La ORDENACION RADIX DE “<<Veces<<” ELEMENTOS:\n\n”;
  for (i = 0; i < n; i++)
    printf(“A[%d] : %d \n”,i,x[i]);
    getch();
  return 0;

}