Algoritmos de ordenamiento por distribución

La ordenación y la búsqueda son operaciones fundamentales en informática. La ordenación se refiere a la operación de organizar datos en algún orden dado, tal como creciente o decreciente para datos numéricos o alfabéticamente para datos de caracteres. La búsqueda se refiere a la operación de encontrar la posición de un ítem dado de entre un conjunto de ítems.

Existen muchos algoritmos de ordenación y búsqueda. En particular, el algoritmo que uno elija dependerá de las propiedades de los datos y de las operaciones que se desee realizar sobre los datos. De acuerdo con esto, queremos saber la complejidad de cada algoritmo; o sea, queremos saber el tiempo de ejecución f(n) de cada algoritmo como una función del número n de elementos de entrada.

Distribución simple

Este algoritmo tiene la siguiente metodología: Ordena el vector tomando cada número e insertándolo en la posición que toma su valor, es decir, tengo un cinco en el arreglo; lo pongo en la posición cinco, algo así como: “lo que valgas en esa posición te pongo”. Por supuesto, no se podrán ordenar los arreglos que tengan valores repetidos y el vector necesita estar del tamaño del número más grande que se encuentre en él.

Principios de distribución

Cuando los datos tienen ciertas características como por ejemplo estar dentro de determinado rango y no haber elementos repetidos, pueden aprovecharse estas características para colocar un elemento en su lugar, por ejemplo:

Origen 0 1 2 3 4 5 6 7 8 9 7 1 3 0 4 2 6 5 8 9

Destino

0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9

A continuación se presenta el código para cambiar los valores del Origen al Destino:

for(int x=0; x<10;x++) 
destino[origen[x=origen[x]; 

¿Que hacer cuando se repitan los datos?

Lo que debemos hacer es incrementar la capacidad de la urna. Para lograrlo podemos hacer lo siguiente:

1.- Definir un arreglo en el que cada posición puede ser ocupada por mas de un registro (un arreglo de arreglo de registros) puede darse la situación de ser insuficiente la cantidad de registros adicionales o de existir demasiado desperdicio de memoria.

2.- Definir el tamaño de la urna variable a través del uso de estructuras como las listas simples enlazadas.

Urna simple

struct nodo 
{ 
_______ info; 
struct nodo *sig; 
} 
nodo *nuevo, *ini[10], *fin[10]; 
int i,p; 
void main() 
{ 
for(i=0;i<10:i++) 
ini=fin=NULL; 
for(i=0;i<n’i++) 
{ 
nuevo=new nodo; 
nuevo->info=A; 
nuevo-> sig=NULL; 
if(ini[A]==NULL) 
ini=fin=nuevo; 
else 
{ 
fin->sig=nuevo; 
fin=nuevo; 
} 
for(i=0,p=0; i<10;i++) 
{ 
nuevo=ini; 
while(nuevo) 
{ 
A[p]=nuevo->info; 
p++; 
ini=nuevo->sig; 
delete nuevo; 
nuevo=ini; 
} 
} 
} 

¿Que hacer cuando el rango de los valores que queremos ordenar es de 100 a 999?

Aplicar urnas simples tantas veces como dígitos tenga el mayor de los números a ordenar. Para la ordenación se hará de la siguiente manera: En la primera pasada se tomará en consideración el digito menos significativo (unidades), en la siguiente vuelta se tomará el siguiente digito hasta terminar (Decenas, Centena,…).

void main() 
{ 
for(cont=1; cont<=veces; cont++) 
{ 
for (y=0; i<n; y++) 
{ 
np=A% (i*10cont); 
np=np/(1* 10 cont - 1 ); 
urnas_simples(); 
} 
} 
}
Politica de Privacidad