radix sort

TRODUCCION


¿Que es un Algoritmo de Ordenamiento ?
Es un algoritmo que nos sirve para ordenar vectores o matrices con un
valor asignado, existen distintos métodos (algoritmos) con distintascaracterísticas y complejidad.

BREVE HISTORIA


1880
Censo

1896
Tabulating
Machine
Company

1890
Herman Hollerith

1911 Fusión
CalculatingTabulatingRecording
Company
(CTR)1924
Thomas Watson

METODO DE RADIX SORT O RAIZ


Es un algoritmo de ordenamiento que ordena enteros procesando
sus dígitos de forma individual. Como los enteros pueden
representar cadenas decaracteres. Radix sort no está limitado sólo a
los enteros.
Este ordenamiento se basa en los valores de los dígitos reales en las
representaciones de posiciones de los números que se ordenan.COMPLEJIDAD
Radix sort es un algoritmo que tiene complejidad
O(n*d)

MEMORIA
O(n)

DESCRIPCION
Consiste en hacer diversos montones de fichas, cada uno caracterizado por
tener en suscomponentes un mismo digito en la misma posición; estos
montones se recogen en orden ascendente.

CLASIFICACION
El de dígito menos significativo (LSD)
El de dígito más significativo (MSD).
- Radix sortLSD
- Radix sort MSD

CARACTERISTICAS


Se encarga de colocar los números en una de las 10 colas
que representan un digito cada una de ella, en estas colas
se colocan los números dependiendodel digito que se esté
analizando.

-

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



-

Reglaspara 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 eldígito más grande en la primera posición en la
cual los dos números no coinciden es el mayor.

-

Este mismo principio se toma para Radix Sort, para visualizar esto
mejor tenemos el siguiente...