Un Algoritmo que me gusta mucho es el quicksort, porque es un algoritmo por demás claro. Ya he escrito lo fácil que es implementarlo en scala, erlang, rust, haskell , F# y lisp.
Ahora le toca a prolog. Básicamente el algoritmo toma un pivot y agrupa los menores del pivot al principio y los mayores al final y aplica quicksort a estos 2 grupos. Y si la lista es vacía o tiene un elemento, ya esta ordenada.
Vamos al código:
quicksort([], []).
quicksort([X], [X]).
quicksort([Pivot|Rest], Sorted) :-
partition(Rest, Pivot, Smaller, Greater),
quicksort(Smaller, SortedSmaller),
quicksort(Greater, SortedGreater),
append(SortedSmaller, [Pivot|SortedGreater], Sorted).
partition([], _, [], []).
partition([X|Rest], Pivot, [X|Smaller], Greater) :-
X =< Pivot,
partition(Rest, Pivot, Smaller, Greater).
partition([X|Rest], Pivot, Smaller, [X|Greater]) :-
X > Pivot,
partition(Rest, Pivot, Smaller, Greater).
Vamos a probarlo:
?- quicksort([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5], Sorted).
Sorted = [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9].
