Radix sort
Equipo:
Castrejón Martínez Yair Eduardo
Flores Salgado Berenice
López Moreno Orlando Dante
Antecedentes
Surgió de la necesidad de llevar una cuenta de tarjetas de censo perforadas. La primera implementación destacable del método Radix Sort de ordenación fue una realización física: la máquina tabuladora eléctrica de Herman Hollerith, utilizada para la ordenación de las tarjetas del censo en USA alrededor del año 1890.
Se dice que este método nació de la idea de Herman Hollerith en 1890, creador de la maquina tabuladora, la cual concatenaba cada hoja dependiendo de la ubicación de las ultimas 3 columnas, que contenían las cifras para el acomodo de tarjetas, estando numerado del 0 al 9. Con la ayuda de este método el censo se vio reducido de 6 semanas a solo unas cuantas horas.
Algoritmo
1.-El primer paso a realizar consiste en tomar un vector de datos a ordenar de tipo entero, pudiendo ser números o letras.
2.-El ordenamiento se puede realizar de dos maneras. (Funcionan de manera similar)
*Usando el bit menos significativo
*Usando el bit más significativo
3.-Cómo primer paso de la implementación se crean 10 colas numeradas de 0 al 9, en cada una de estas se almacenaran los valores que tengan el valor de la posición del bit con la que se esté trabajando.
Tomando como ejemplo un ordenamiento en base al bit menos significativo, y usando una variable n siendo esta igual al número de dígitos máximo en el vector.
4.-Se toma el n bit de cada valor del vector, dependiendo cual sea este se guarda el valor que está en el vector dentro de la cola numerada con ese digito (por ejemplo si tenemos un 10, este se almacenara en la cola 0).
5-Se repetirá el paso anterior m veces siendo m el número de datos en el vector.
6.-Se restara 1 a n, y se repetirán los pasos 4,5 y 6 hasta que n sea igual a 0.
7.-Al final se obtendrán los datos ordenados.
Tiempos de ejecución
Big O
Omega
Aplicación
Aplicación a la computación paralela.
La computación paralela es una forma de cómputo en la que muchas instrucciones se ejecutan simultáneamente. En el caso de la computación paralela cada bit se pasa al siguiente procesador disponible. Un único procesador sería utilizado al inicio (bit más significativo) y entre el segundo y tercer dígito se dedican todos los procesadores disponibles. Lo que se busca es que cada subdivisión esté totalmente ordenada, para así utilizar menos procesadores.
Simulación
Bibliografía
Algoritmos y estructura de datos "Una perspectiva en C" Autor Luis Joyanes Aguilar,Ignacio Zahonero Martinez
C++ Data Estructures, Nell Dale, David Tegure, Jones & Bartlett
Mastering Algorithms with C, Kyle Loudon, O' Reilly, 1era Edicion.
Fundamentos de programación y estructuras de datos y objetos, LUIS JOYANES AGUILAR , S.A. MCGRAW-HILL / INTERAMERICANA DE ESPAÑA, 2003
