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 comprendidos entre 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 pasada utilizar 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 = 0){i = left; j = right;while (j != i){while (!a.bits (bit, 1) && i 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);}}Este mé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 se tengan, 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 llaves iguales 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 la que 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 son estables, pero la mayoría de los métodos sofisticados no lo son. Curiosidades y tops de internet
Ordenamiento por radix directo
Una variante al método de intercambio radix consiste en examinar los bits de derecha a izquierda. El método depende de que el proceso de partición de un bit sea estable. Por lo que el proceso de partición utilizado en el algoritmo de intercambio radix no nos sirve; el proceso de partición es como ordenar una estructura con solo dos valores, por lo que el algoritmo de distribución por conteo nos sirve muy bien. Si asumimos que M = 2 en el algoritmo de distribución por conteo y reemplazamos a por bits (a, k, 1) podemos ordenar el arreglo a en sus k posiciones menos significativas usando un arreglo temporal b. Pero nos conviene más usar un valor de M mayor que corresponda a m bits a la vez durante el ordenamiento con M = 2m como en el siguiente código.
void straightradix (itemType a[], itemType b[], int N){int i, j, pass, count [M-1];for (pass = 0; pass 
ORDENACION RADIX ESTRUCTURA DATOS C#
Un problema que se presenta con frecuencia es el siguiente: 'Ordenar un archivo con N registros cuyas llaves son enteros comprendidos entre 0 y M-1'. Si M no e
adsl
es
https://adsltodo.es/static/images/adsl-ordenacion-radix-estructura-datos-c-1269-0.jpg
2024-11-19
El contenido original se encuentra en https://programacionfacil.com/estructura_datos_csharp/ordenacion_radix/
Todos los derechos reservados para el autor del contenido original (en el enlace de la linea superior)
Si crees que alguno de los contenidos (texto, imagenes o multimedia) en esta página infringe tus derechos relativos a propiedad intelectual, marcas registradas o cualquier otro de tus derechos, por favor ponte en contacto con nosotros en el mail [email protected] y retiraremos este contenido inmediatamente