% nacteni:
/* ['2.5.1_10.pl']. */

qsort([],[]).
qsort([H],[H]) :- !.
qsort([H|T],L) :- divide(H,T,M,V),
                  qsort(M,M1), qsort(V,V1),
                  append(M1,[H|V1],L).
divide(_,[],[],[]).
divide(H,[K|T],[K|M],V) :- K=<H, !, divide(H,T,M,V).
divide(H,[K|T],M,[K|V]) :- divide(H,T,M,V).

% demonstracni vypis

write_long_list([X1,X2,X3,X4,X5,X6,X7,X8,X9,X10|T]) :-
    write('['), write(X1), write(','), write(X2), write(','), write(X3),
    write(','), write(X4), write(','), write(X5), write(','), write(X6),
    write(','), write(X7), write(','), write(X8), write(','), write(X9),
    write(','), write(X10), write(',...,'), last(T,X), write(X), write(']').

start:- 
    write('Radici algoritmus QuickSort'),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,
    write('Vysledek volani "qsort([... 300 000 nahodnych cisel...], L2)":'),nl,
    length(Xs, 300000), maplist(random(0,1000000), Xs),
    qsort(Xs, L2), write('L2 = '),write_long_list(L2),nl.

?-start.

Radici algoritmus QuickSort

Vysledek volani "qsort([5, 2, 8, 2, 654, 8, 3, 4], L)":
L = [2,2,3,4,5,8,8,654]
Vysledek volani "qsort([... 300 000 nahodnych cisel...], L2)":
L2 = [4,4,5,17,26,26,30,37,38,50,...,999999]

#!/usr/bin/env python
# encoding=utf-8 (pep 0263)

from linked_lists import LinkedList, Cons, Nil

def append(xs, ys):
    if xs == Nil:
        return ys
    else:
        return Cons(xs.head, append(xs.tail, ys))

def qsort(xs):
    if xs == Nil:
        return Nil
    if xs.tail == Nil:
        return xs
    ms, vs = divide(xs.head, xs.tail)
    return append(qsort(ms), Cons(xs.head, qsort(vs)))

def divide(h, xs):
    if xs == Nil:
        return (Nil, Nil)
    ms, vs = divide(h, xs.tail)
    if xs.head <= h:
        return (Cons(xs.head, ms), vs)
    else:
        return (ms, Cons(xs.head, vs))

# demonstracni vypis
if __name__ == "__main__":
    print("Radici algoritmus QuickSort\n")
    print("qsort(LinkedList([5, 2, 8, 2, 654, 8, 3, 4])): \n\t%s\n" % \
            qsort(LinkedList([5, 2, 8, 2, 654, 8, 3, 4])))

Radici algoritmus QuickSort

qsort(LinkedList([5, 2, 8, 2, 654, 8, 3, 4])): 
	[2, 2, 3, 4, 5, 8, 8, 654]