Ordenamiento de burbuja en Ruby

Nuevamente estoy intentando aprender Ruby, pero para ser honesto se me dificulta un poco, esta tan optimizado que muchas cosas se pueden hacer en prácticamente en una solo línea. Además tengo muchos vicios de otros lenguajes, principalmente … por favor no se burlen…¡BASIC!.

Entonces recordé la forma en que aprendí otros lenguajes como Pascal o C y fue haciendo algoritmos clásicos.

Una serie de algoritmos clásicos son los de ordenamiento. Empecé con el más sencillo conocido como Ordenamiento de burbuja o Bubble Sort.

Es fácil de entender, se van comparando los elementos de una lista de manera ordenada en pares, si un par esta desordenado, intercambia sus lugares. Cuando se termina esta “pasada” se vuelve a empezar, hasta que ya no se hacen intercambios, en ese momento la lista esta ordenada.

Algoritmo de burbuja: wikipedia

Les dejo el código que desarrolle en Ruby, abunda en comentarios, en este caso se hace uso de arreglos y sus índices, también el manejo de bucles y condiciones, vamos que es un ejemplo redondo.

#!/usr/bin/env ruby

# Aprendiendo ruby de mala manera.
# ================================
#
# Algoritmo de ordenamiento de burbuja
#
# Aclaración:
# Ruby es un lenguaje que tiene muchas ventajas, incluyendo metodos de 
# ordenamiento, sin embargo, como una forma de irme familiarizando con el
# lenguaje haré algoritmos clásicos de ordenamiento.
#
# Si quieren conocer más detalles sobre este algoritmo, pueden consultar
# la wikipedia http://en.wikipedia.org/wiki/Bubble_sort
#
# a y b son arreglos idénticos.
#
# autor: Francisco J. de la Torre (aka LinuxmanR4) web: http://linuxmar4.com
# sáb 25 may 2013 12:19:30 CDT 

a = [99,86,48,16,82,50,25,62,8,45]  #Será ordenado mediante bubble sort
b = [99,86,48,16,82,50,25,62,8,45]  #Al estilo Ruby

# Empezamos con el ordenamiento burbuja en el arreglo a.
# ------------------------------------------------------

# ¿Cuantos elementos tiene el arreglo?
n = a.count - 1

# count es un método, en este caso regresa 10 pero el indice del arreglo
# empieza en cero o sea, de cero a nueve, por eso le quito uno.

# Los índices en ruby comienzan en cero, por eso a[0] = 99 , a[1] = 86

begin
	intercambio = false
	i = 1
	while i <= n do
		if a[i-1] > a[i] # Si se cumple la condición, entonces intercambiamos.
			aux = a[i-1]
			a[i-1] = a[i]
			a[i] = aux
			intercambio = true
		end # if
    	i +=1 # El equivalente a i = i + 1 
	end #while i

end while intercambio == true # Este ciclo se ejecuta mientras haga intercambios.

# Llegó el momento de mostrar los resultados.

# Arreglo ordenado con bubble sort.
# join lo uso para mostrar el arreglo separado por comas.

puts "a = " << a.join(" , ")

# Ahora la forma ruby.
puts "b = " << b.sort.join(" , ")

Al final del programa muestro como se debería de hacer el ordenamiento de un arreglo usando el método sort de Ruby que hace todo el trabajo en una sola línea de código.

Para aprender más sobre Ruby.

Estos sitios me han ayudado mucho para familiarizarme con Ruby y su filosofía:

Actualización

Atendiendo a los comentarios del maestro Gunnar Wolf hice la siguiente versión de este algoritmo de ordenación. Agregando un método a la clase Array de nombre swap que se encarga de hacer el intercambio de valores en el arreglo. Y usando times para hacer el recorrido de todos los índices del arreglo.

#!/usr/bin/env ruby

# Aprendiendo ruby de mala manera.
# ================================
#
# Algoritmo de ordenamiento de burbuja
#
# Aclaración:
# Ruby es un lenguaje que tiene muchas ventajas, incluyendo metodos de 
# ordenamiento, sin embargo, como una forma de irme familiarizando con el
# lenguaje haré algoritmos clásicos de ordenamiento.
#
# Si quieren conocer más detalles sobre este algoritmo, pueden consultar
# la wikipedia http://en.wikipedia.org/wiki/Bubble_sort
#
# a y b son arreglos idénticos.
#
# autor: Francisco J. de la Torre (aka LinuxmanR4) web: http://linuxmar4.com
# sáb 25 may 2013 12:19:30 CDT 
# Con observaciones de Gunnar Wolf. web: http://gwolf.org/

# Empezamos con el ordenamiento burbuja en el arreglo a.
# ------------------------------------------------------

# El método swap sirve para intercambiar de posición los elementos de un arreglo.
class Array
    def swap(a,b)
        self[a], self[b] = self[b], self[a]
    end
end

a = [99,86,48,16,82,50,25,62,8,45]  #Será ordenado mediante bubble sort
b = [99,86,48,16,82,50,25,62,8,45]  #Al estilo Ruby

begin
	intercambio = false
	(a.count-1).times do |i|
		if a[i] > a[i+1]  # Si se cumple la condición, entonces intercambiamos.
			a.swap(i,i+1)
			intercambio = true
		end # if
		next
	end # times
end while intercambio == true # Este ciclo se ejecuta mientras haga intercambios.

# Llegó el momento de mostrar los resultados.

# Arreglo ordenado con bubble sort.
# join lo uso para mostrar el arreglo separado por comas.

puts "a = " << a.join(" , ")

# Ahora la forma ruby.
puts "b = " << b.sort.join(" , ")

4 comentarios en «Ordenamiento de burbuja en Ruby»

  1. Buff, qué bajón la manera en que tu blog se come el formato que hice con tanto cuidado 🙁 Espero quede comprensible lo que escribí.

    Responder
    • Tienes razón Gunnar, el algoritmo que presento es más o menos el mismo que muestra en la wikipedia y con tus recomendaciones llegó la hora de mejorarlo. Creo que por eso le puse al algoritmo «a la mala». 🙂

      Vi que tus comentarios con código fueron masacrados por mi blog (creo que el culpable es markdown), por eso tengo a la mano una herramienta para compartir código, de hecho pudiste colocar una respuesta a ese código en paste.linuxmanr4.com

      Lo que voy a hacer es hacerlo el mismo algoritmo siguiendo tus recomendaciones y lo voy a publicar como parte del artículo.

      Saludos !!!

      Responder
  2. Bien dicen que se puede escribir C en cualquier lenguaje 😉

    Va una pequeña sugerencia estilística — Si quieres trabajar en Ruby, hay que seguir los caminos de Ruby. Me centro en el bloque central, donde haces todo el trabajo «real»:

    • Podemos evitar a la innecesaria variable n , y a i fuera de su ámbito, y a un while (que no usams para avanzar sobre un ciclo) usando times sobre un entero
    • En vez de envolver la «acción» en un if, mejor usamos el condicional para brincar cuando no hay trabajo por realizar
    • Evitamos el uso de la variable aux y reducimos las asignaciones a una sola. Podemos hacer dos asignaciones al mismo tiempo.

    (…)

    begin
            intercambio = false
            (a.count-1).times do |i|
                    next if a[i] >= a[i-1]
                    a[i], a[i-1] = a[i-1], a[i]
                    intercambio = true
            end #times

    end while intercambio == true # Este ciclo se ejecuta mientras haga intercambios.

    Me parece que queda mucho más fácil de leer.

    Ahora, si quisieras realmente hacerlo al estilo Ruby, podrías hacer «monkey patching» y modificar Array, o hacer que a sea de otra clase que herede de Array y le agregue este comportamiento. Por ejemplo:

    class Array
        def swap(a,b)
            self[a], self[b] = self[b], self[a]
        end
    end
    

    Con esto, el intercambio entre a[i] y a[i-1] podría remplazarse por un más claro a.swap(i, i-1).

    Parte de lo bonito de Ruby es que… entre más miras el código, más puedes afinarlo 🙂

    Responder
    • Listo Gunnar, acabo de publicar el nuevo algoritmo con tus sugerencias, solo hice algunos pequeños ajustes, detallitos en los índices del arreglo.

      Responder

¡Me encantaría saber que opinas!

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.