• Author / Uploaded
• luisrincon782165

• Categories
• Cola (tipo de datos abstractos)
• Estructura de datos de matriz
• Algoritmos
• Algoritmos y Estructuras de Datos
• Programación de computadoras

Citation preview

Dar una descripción breve pero completa del algoritmo. Preferiblemente, debería proveerse pseudocódigo. Algoritmo Radix sort Es un algoritmo de ordenamiento en la programación ordena enteros a partir de sus dígitos de forma individual. El método de ordenación por residuos, o RadixSort, utiliza una aproximación diferente a la de comparar los elementos del arreglo entre sí. En vez de esto, este algoritmo recorre el arreglo trasladando cada elemento a una cola determinada por el residuo, o dígito menos significativo del número. Cuando todos los elementos han sido trasladados a las colas, se recorren todas las colas en orden trasladando ahora los elementos al vector. El proceso se repite ahora para los demás dígitos de los elementos del vector. A continuación, se muestra la implementación en Java utilizando un enfoque genérico public static void ordenacionResiduos(int[] v) { int max = 1; // cantidad de repeticiones int nbytes = 4; // numero de bytes a desplazar int nColas = (int) Math.pow(2,nbytes) ; // Creación e inicialización del arreglo de colas Queue[] cola = new LinkedList[nColas]; for(int i=0; i>div) & 0xf; cola[numCola].add(numero); } div = div+nbytes; // parte 2: recorrer las colas en orden para poner cada // elemento en el vector; int j=0; for(Queue c: cola) { while(!c.isEmpty()) v[j++]=c.remove(); } // la primera vez se actualiza el número de veces que se // debe ejecutar el proceso if(i==0) { max = (int) (Math.log(max)/Math.log(nColas)) + 1; }

Ordenamiento de raíz (radix sort). Este ordenamiento se basa en los valores de los dígitos reales en las representaciones de posiciones de los números que se ordenan. Por ejemplo, el número 235 se escribe 2 en la posición de centenas, un 3 en la posición de decenas y un 5 en la posición de unidades. Reglas para ordenar. Empezar en el dígito más significativo y avanzar por los dígitos menos significativos mientras coinciden los dígitos correspondientes en los dos números. El número con el dígito más grande en la primera posición en la cual los dígitos de los dos números no coinciden es el mayor de los dos (por supuesto sí coinciden todos los dígitos de ambos números, son iguales). Este mismo principio se toma para Radix Sort, para visualizar esto mejor tenemos el siguiente ejemplo. En el ejemplo anterior se ordenó de izquierda a derecha. Ahora vamos a ordenar de derecha a izquierda.

25 57 48 37 12 92 86 33

Asignamos colas basadas en el dígito menos significativo. Parte delantera Parte posterior 0 1 212 92 333 4 525 686 757 37 848