Ordenamiento rápido o Quick sort es otro algoritmo clásico de ordenamiento.
Animación del algoritmo quick sort – wikipedia
En este algoritmo se usa un pivote que sirve para separar el arreglo, con el fin de dividir el ordenamiento en partes más pequeñas. La elección del pivote se puede realizar de varias maneras, pero en este caso elegí la más sencilla que es el elemento que esta en medio del arreglo.
Como pueden ver, el manejo de arreglos que hace Ruby está para dar miedo, luego viene la recursividad que es básicamente cuando el método se llama nuevamente a sí mismo.
#!/usr/bin/env ruby
# Aprendiendo ruby de mala manera.
# ================================
#
# Algoritmo de ordenamiento rápido - Quick Sort
#
# 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 https://es.wikipedia.org/wiki/Quicksort
#
# autor: Francisco J. de la Torre (aka LinuxmanR4) web: http://linuxmar4.com
# mar 28 may 2013 13:28:20 CDT
#
a = [99,86,48,16,82,50,25,62,8,45] #Será ordenado mediante quick sort.
class Array
def quick_sort # el métoodo quick_sort será el encargado de ordenar recursivamente el arreglo.
return self if length <= 1 # si el tamaño del arreglo es menor o igual a 1 no hay nada que ordenar.
pivote = self[length / 2] # La elección del pivote en este caso, es el elemento al centro del arreglo.
find_all { |i| i < pivote }.quick_sort + # se ordenan recursivamente todos los elementos más pequeños que el pivote
find_all { |i| i == pivote } + # más los elementos que son igual que el pivote
find_all { |i| i > pivote}.quick_sort # y se ordenan recursivamente los elementos más grandes que el pivote
end
end
puts "a = " << a.quick_sort.join(" , ")
Hay varias curiosidades en este ejemplo.
- self es un objeto muy interesante, porque en ruby, durante cada instrucción, solo se puede manejar un objeto a la vez y self es ese objeto. Durante la recursividad se van a manejar una gran cantidad de subarreglos más pequeños, de esta manera logramos hacerlo sin declarar otra variable.
- El método find_all que devuelve otro arreglo que cumpla con la condición, en este caso valores más grandes o pequeños que el pivote.
Como pueden ver Ruby es un lenguaje con un alto nivel de optimización, entre más lo conozco, más quiero seguir aprendiendo.