Quicksort en Erlang

Una implementación ingenua de Quicksort funciona tomando el primer elemento de una lista, el pivote, y luego colocando todos los elementos más pequeños o iguales al pivote en una nueva lista, y todos los más grandes en otra lista. Luego tomamos cada una de estas listas y hacemos lo mismo con ellas hasta que cada lista se hace cada vez más pequeña. Esto continúa hasta que no tenga nada más que una lista vacía para ordenar, que será nuestro caso base. Se dice que esta implementación es ingenua porque las versiones más inteligentes de Quicksort intentarán elegir pivotes óptimos para ser más rápidos. Sin embargo, eso realmente no nos importa para nuestro ejemplo.

Necesitaremos dos funciones para esto: una primera función para dividir la lista en partes más pequeñas y más grandes y una segunda función para aplicar la función de partición en cada una de las nuevas listas y unirlas. En primer lugar, escribiremos la función de pegamento:

quicksort([]) -> [];

quicksort([Pivot|Rest]) ->

{Smaller, Larger} = partition(Pivot,Rest,[],[]),

quicksort(Smaller) ++ [Pivot] ++ quicksort(Larger).

Esto muestra el caso base, una lista ya dividida en partes más grandes y más pequeñas por otra función, el uso de un pivote con ambas listas ordenadas rápidamente añadidas antes y después. Entonces esto debería encargarse de armar listas. Ahora la función de partición:

partition(_,[], Smaller, Larger) -> {Smaller, Larger};

partition(Pivot, [H|T], Smaller, Larger) ->

if H =< Pivot -> partition(Pivot, T, [H|Smaller], Larger);

H >  Pivot -> partition(Pivot, T, Smaller, [H|Larger])

end.

Y ahora puede ejecutar su función de clasificación rápida. Si ha buscado ejemplos de Erlang en Internet antes, es posible que haya visto otra implementación de clasificación rápida, una que es más simple y fácil de leer, pero que utiliza listas por comprensión. Las piezas fáciles de reemplazar son las que crean nuevas listas, la función partición/4:

lc_quicksort([]) -> [];

lc_quicksort([Pivot|Rest]) ->

lc_quicksort([Smaller || Smaller <- Rest, Smaller =< Pivot])

++ [Pivot] ++

lc_quicksort([Larger || Larger <- Rest, Larger > Pivot]).

Las principales diferencias son que esta versión es mucho más fácil de leer, pero a cambio, tiene que recorrer la lista dos veces para dividirla en dos partes. Esta es una lucha entre la claridad y el rendimiento, pero el verdadero perdedor aquí eres tú, porque ya existe una función listas:ordenar/1. Usa ese en su lugar.

Toda esta concisión es buena para fines educativos, pero no para el rendimiento. ¡Muchos tutoriales de programación funcional nunca mencionan esto! En primer lugar, aquí ambas implementaciones deben procesar valores que sean iguales al pivote más de una vez. En su lugar, podríamos haber decidido devolver 3 listas: elementos más pequeños, más grandes e iguales al pivote para hacerlo más eficiente.