quicksort( Unsorted, Sorted ) :- qsort ( Unsorted, Sorted, [ ] ).
qsort ( [ X | Unsorted] , Sorted, Rest) :- partition ( Unsorted, X, Smaller, Larger ),
                                                             qsort ( Smaller, Sorted, [X | Sorted1] ),
                                                             qsort ( Larger, Sorted1, Rest).
qsort ( [ ], Rest, Rest).
partition ( [X | Xs], A, Smaller, [X | Larger]) :- A<X : partition( Xs, A, Smaller, Larger).
partition ( [X | Xs], A, [X | Smaller], Larger) :- A>=X : partition( Xs, A, Smaller, Larger).
partition ( [ ], _ , [ ], [ ]).

O passo i é o resultado da redução dos objetivos do passo i-1.
Os números internos das setas indicam a regra do programa usada.
As setas cheias indicam suspensão por redução.
As linhas pontilhadas indicam onde as unificações feitas estavam sendo esperadas.
Para poupar espaço foi substituído partition por p e qsort por q.

Voltar