Sistemas

Ordenamiento Radix
Ordenamiento de distribución por conteo
Un problema que se presenta con frecuencia es el siguiente: “Ordenar un archivo con N registros cuyas llaves son enteros comprendidosentre 0 y M-1”. Si M no es muy grande, se puede usar el algoritmo de distribución por conteo. La idea básica es contar el número de veces que se repite cada llave diferente y en una segunda pasadautilizar el conteo para posicionar los registros en el archivo.
void distributioncounting (itemType a[], int N, int M)
{
itemType *b;
b = new itemType [N];
int *count;
count = new int[M];
int i, j;for (j = 0; j < M; j++) count [j] = 0;
for (i = 1; i = 1; i--) b[count[a]--] = a ;
for (i = 1; i left && bit >= 0)
{
i = left; j = right;
while (j != i)
{
while (!a.bits (bit, 1) && i < j)i++;
while ( a[j].bits (bit, 1) && j > i) j--;
swap (a, i, j);
}
if (!a[right].bits (bit, 1)) j++;
radixexchange (a, left, j - 1, bit - 1);
radixexchange (a, j, right, bit - 1);
}
}
Estemétodo se emplea para organizar información por mas de un criterio. Lo que hacemos es determinar la importancia de los criterios de ordenación y aplicar ordenación estable tantas veces como criterios setengan, empezando por el criterio menos importante y determinando por el criterio más importante.
Estabilidad
Un algoritmo de ordenamiento se considera estable si preserva el orden relativo de llavesiguales en la estructura de datos. Por ejemplo, si queremos ordenar por calificación una lista de asistencia que se encuentra ordenada alfabéticamente, un algoritmo estable produce una lista en laque los estudiantes con el mismo grado se mantienen ordenados alfabéticamente, mientras que un algoritmo inestable no dejará trazas del ordenamiento original. La mayoría de los métodos básicos sonestables, pero la mayoría de los métodos sofisticados no lo son.
Ordenamiento por radix directo
Una variante al método de intercambio radix consiste en examinar los bits de derecha a izquierda. El...