% nacteni:
/* ['2.5.2_11.pl']. */

:- retractall(start/0).
:- retractall(qsort/2).
:- retractall(divide/4).
:- dynamic
       qsort/2,
       divide/4.

qsort(L,S):- qsort_dl(L,S-[]).
qsort_dl([], A-A).
qsort_dl([H|T],A-B):- divide(H,T,L1,L2),
qsort_dl(L2,A1-B),
qsort_dl(L1,A-[H|A1]).
divide(_,[],[],[]) :- ! .
divide(H,[K|T],[K|M],V):- K=<H, !, divide(H,T,M,V).
divide(H,[K|T],M,[K|V]):- K>H, divide(H,T,M,V).

% demonstracni vypis

:- dynamic
       start/0.
       
start:- 
    write('Radici algoritmus QuickSort - efektivnejsi varianta'),
    write(' s rozdilovymi seznamy'),nl,nl,
    write('Vysledek volani "qsort([5, 2, 8, 2, 654, 8, 3, 4], L)":'),nl,
    qsort([5, 2, 8, 2, 654, 8, 3, 4], L), write('L = '),write(L),nl.

?-start.

:- retractall(start/0).
