I Algoritmo de la burbuja (bubble sort) 6
La ordenación por burbuja es uno de los 8
métodos más fáciles de ordenación. El método
10
(algoritmo) de ordenación es muy simple. Se
compara cada elemento del array con el Figura 1 secuencias de
siguiente (por parejas), si no están en el orden ordenación
correcto, se intercambian entre sí sus valores. El La ordenación de
valor más pequeño flota hasta la parte superior arrays requiere siempre un intercambio de
del array como si fuera una burbuja en un vaso valores, cuando éstos no se encuentran en el
de refresco con gas. orden previsto. Si, por ejemplo, en la primera
pasada 6 y 4 no están ordenados se han de
La Figura 1 muestra una lista de números,
intercambiar sus valores. Suponiendo que el
antes, durante las sucesivas comparaciones y a
array se denomina lista:
la terminación del algoritmo de la burbuja. Se
van realizando diferentes pasadas hasta que la Lista [0] 6
lista se encuentra ordenada totalmente en orden
ascendente. Lista [0] 4
Lista desordenada Lista [ 0] 10
6 4 10 2 8 Lista [0] 2
Primera pasada Lista [0] 8
6 4 4 4 4 para intercambiar dos valores, se necesita
utilizar una tercera variable auxiliar que
6 6 6 10 10 contenga el resultado inmediato. Así, por
2 2 2 2 10 ejemplo, si las dos variables son 1 i s t a [ O I y
1 1 s t a [ 1 1 , el siguiente código realiza el
intercambio de dos variable
8 8 8 8 10
aux = lista[0]
Segunda pasada
Lista[0] = Lista[1]
4 4
Lista[1] = aux;
6 2
La función intercambio intercambia los valores
2 6 de dos variables x e y El algoritmo de
intercambio utiliza una variable auxiliar
8 8
aux = x;
10 10 x = y;
Tercera pasada y = aux;
4 2 La función intercambio sirve para intercambiar
dos elementos x e y que se pasan a ella. Al tener
2 4 que pasar por referencia, los argumentos de la
función son punteros.
6 6
Void intercambio (float*X ; float’’ y){
8 8
float aux;
10 10 aux = *x;
Cuarta pasada *X = *Y;
2 *Y = aux ;
4 Una llamada a esta función:
float r , v; Implementación en C
intercambio( &r, &v), Aquí tienes una implementación de Radix Sort
para enteros en C:
El programa siguiente ordena una lista de
números reales y a continuación los imprime.
Algoritmo de ordenación por distribución
(Radix Sort)
Radix Sort es un algoritmo de ordenación que
clasifica números enteros procesando sus dígitos
individuales. Se basa en el principio de ordenar
primero por el dígito menos significativo (LSD)
y luego pasar al siguiente dígito más
significativo, o viceversa. Radix Sort es
eficiente para números enteros y funciona bien
cuando el rango de dígitos es limitado
El algoritmo Radix Sort consta de los siguientes
pasos:
1. Encontrar el número máximo en el array
para determinar el número de dígitos en el
número más grande.
2. Ordenar los números basándose en cada
dígito, comenzando por el dígito menos
significativo.
3. Utilizar un algoritmo de conteo para
ordenar los números según el dígito actual.
Explicación del Código
1. Función conteoOrdenar:
o Ordena los elementos según el dígito
representado por exp (unidades, decenas,
centenas, etc.).
o Usa un algoritmo de conteo para organizar
los números en el array output[].
2. Función radixSort:
o Encuentra el número máximo en el array
para determinar el número de dígitos del
número más grande.
o Llama a conteoOrdenar para cada lugar de
dígito, desde el menos significativo hasta el
más significativo.
3. Función imprimir Array:
o Imprime los elementos del array.
Puntos Clave:
Eficiencia: Radix Sort es eficiente cuando
el rango de dígitos (o claves) no es muy
grande.
Ordenación estable: El algoritmo es
estable porque utiliza el conteo como
subrutina, lo que preserva el orden de los
elementos iguales.
Esta implementación de Radix Sort en C te
permitirá ordenar un array de enteros utilizando
el algoritmo de ordenación por distribución.