bubblesort(S,Sorted)
Seznam S setřiďte tak, že
■ nalezněte první dva sousední prvky X a Y v S tak, že X>Y, vyměňte pořadí X a Y a získate SI; a setřiďte SI
Třídění, rOZdílOVé S6Znamy ■ pokud neexistuje žádný takový pár sousedních prvků X a Y,
pak je S setříděný seznam
swap([X,Y|Rest],[Y,X|Restl]) :-
X>Y. % nebo obecněji X@>Y pomoci gt(X,Y)
swap([Z|Rest],[Z|Restl]) :-
swapCRest,Restl).
bubblesortCS,Sorted) :-
swap (S,SI),  ! ,
bubblesortCSl, Sorted). bubblesortCSorted,Sorted).
Hana Rudová, Logické programování I, 27. března 2007 2 Třídění, rozdílové seznamy
qui cksort(S,Sorted)
Neprázdný seznam S setřiďte tak, že
■ smažte nějaký prvek X z S;
rozdělte zbytek S na dva seznamy Small a Big tak, že: v Big jsou větší prvky než X a v Small jsou zbývající prvky
■ setřiďte Small do SortedSmall
■ setřiďte Big do SortedBig
■ setříděný seznam vznikne spojením SortedSmall a [XISortedBig]
quicksort([] , []) . quicksort([X|T], Sorted)
+ ošetření případu, kdy S je prázdný seznam splitCX, Tail, Small, Big), quicksortCSmall, SortedSmall), quicksort(Big, SortedBig), appendCSortedSmall, [XISortedBig], Sorted).
splitCX, [],  [], []).
splitCX,  [Y|T],  [Y|Small], Big)
splitCX,  [Y|T], Small,  [Y|Big])
Hana Rudová, Logické programování I, 27. března 2007
X>Y,   !, splitCX, T, Small, Big). splitCX, T, Small, Big).
3 Třídění, rozdílové seznamy
Rozdílové seznamy
Zapamatování konce a připojení na konec: rozdílové seznamy
[a,b] = L1-L2 = [a,b|T]-T = [a,b,c|S]-[c|S] = [a,b,c]-[c]
Reprezentace prázdného seznamu: L-L
A1
Z1 A2
Z2
L1
	
L2	
L3
?- append( [1,2,3|Z1]-Z1,   [4,5|Z2]-Z2, S ).
append( Al-Zl, Z1-Z2, A1-Z2 ). LI        L2 L3
Hana Rudová, Logické programování I, 27. března 2007
Třídění, rozdílové seznamy
reverse(Seznam, Opacny)
quicksort pomocí rozdílových seznamů
reverseC [] ,  [] ) .
reverseC [ H | T ], Opacny ) :-
reverseC T, OpacnyT ),
appendC OpacnyT,  [ H ], Opacny ).
reverseC Seznam, Opacny ) :- reverseOC Seznam, Opacny-[]). reverseOC [] , S-S ) .
reverseOC [ H | T ], Opacny-OpacnyKonec   ) :-
reverseOC T,   Opacny-[ H | OpacnyKonec] ).
reverseC Seznam, Opacny ) :- reverseOC Seznam,  [], Opacny ).
reverseOC □ , S, S ).
reverseOC [ H | T ], A, Opacny ) :-
reverseOC T,  [ H | A ], Opacny ).
Hana Rudová, Logické programování I, 27. března 2007 5 Třídění, rozdílové seznamy
Neprázdný seznam S setřiďte tak, že
■ smažte nějaký prvek X z S;
rozdělte zbytek S na dva seznamy Small a Big tak, že: v Big jsou větší prvky než X a v Small jsou zbývající prvky
■ setřiďte Small do SortedSmall
■ setřiďte Big do SortedBig
■ setříděný seznam vznikne spojením SortedSmall a [XISortedBig]
quicksortCS, Sorted) :- quicksortlCS,Sorted-[]).
quicksortC[] ,Z-Z) . quicksortC[X|T], A1-Z2) :-
splitCX, Tail, Small, Big),
quicksortCSmall, A1-[X|A2]),
quicksortCBig,   A2-Z2). append(Al-Zl, Z1-Z2, A1-Z2).
Hana Rudová, Logické programování I, 27. března 2007 6 Třídění, rozdílové seznamy