LISTA SIMPLE
LISTA SIMPLE
RADIX
RadixSort
Es un algoritmo de ordenamiento que ordena enteros procesando sus dígitos de forma individual.
¿Cómo funciona?
•Procesa las representaciones de enteros empezando por el LSD y moviéndose hacía MSD
•Empezar por el LSD y avanzar por los LSD mientras coinciden los dígitos correspondientes en los dos números.
•Se repite tantas veces como el tamaño del mayor de los números a ordenar
•El ordenamiento es eficiente si el número de dígitos no es demasiado grande
•Se requiere conocer la cantidad de dígitos del valor máximo
Arreglo de listas
Se utilizara un arreglo de listas para ordenar en la posición correcta cada elemento de nuestra lista, el arreglo iniciará en 0 y terminará en 9
Ejemplo:
Colocaremos cada elemento de la lista, en la posición que le corresponda, de acuerdo a su bit menos significativo(color rojo)
Sacaremos en orden del arreglo cada elemento insertado, para colocarlos de nuevo en una lista
Repetimos el método, ahora con el siguiente dígito de cada número
Sacaremos en orden del arreglo cada elemento insertado, para colocarlos de nuevo en una lista, y como el número más grande de nuestra lista, solo tiene 2 dígitos, el número de veces que se repite el método es 2, por lo tanto ya terminados de ordenar la lista.
QUICKSORT
QuickSort
Es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional.
Básicamente:
Se toma un elemento como pivote, debemos lograr que todos los elementos de lado derecho sean mayores al pivote, y los elementos de lado izquierdo sean menores al pivote, logrado este paso, se formarán sublistas en cada lado del pivote, y de nueva cuenta repetiremos el método, hasta ordenar la lista.
Ejemplo:
SHELL
Shell
El algoritmo Shell es una mejora de la ordenación por inserción, donde se van comparando elementos distantes, al tiempo que se los intercambian si corresponde. A medida que se aumentan los pasos, el tamaño de los saltos disminuye; por esto mismo, es útil tanto como si los datos desordenados se encuentran cercanos, o lejanos.
Pasos/ejemplo:
1. El total de número de elementos de nuestra lista se divide entre dos.
8/2=4
2. Iniciando con i=0, comparamos el elemento i con el elemento i+4
8<9 = hay intercambio
12<6= no hay intercambio
4<10= hay intercambio
14<7 = no hay intercambio
Por lo tanto, después de hacer los intercambios, la lista queda:
Se vuelve a dividir en 2 grupos:
4/2=2
Buscamos el elemento menor de cada subgrupo y los intercambiamos entre ellos en orden ascendente
Por lo tanto, después de hacer los intercambios, la lista queda:
La lista se ordenó
