Różnice

Różnice między wybraną wersją a wersją aktualną.

Odnośnik do tego porównania

pl:prolog:pllib:quicksort_2 [2019/06/27 15:50] (aktualna)
Linia 1: Linia 1:
 +====== Quicksort 2 ======
 +{{tag>​sorting algorithms recursion}}
 +===== Description =====
 +Program implements quicksort algorithm.
 +
 +**Source**: ​ PROLOG programming for artificial intelligence,​ 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7.
 +===== Download =====
 +Program source code: {{quicksort_2.pl}}
 +===== Listing =====
 +<code prolog>
 +% Figure 9.3  A more efficient implementation of quicksort using difference-pair
 +% representation for lists. ​
 +
 +
 +% quicksort( List, SortedList):​ sort List with the quicksort algorithm
 +
 +quicksort( List, Sorted) ​ :-
 +  quicksort2( List, Sorted - [] ).
 +
 +% quicksort2( List, SortedDiffList):​ sort List, result is represented as difference list
 +
 +quicksort2( [], Z - Z).
 +
 +quicksort2( [X | Tail], A1 - Z2)  :-
 +   ​split( X, Tail, Small, Big),
 +   ​quicksort2( Small, A1 - [X | A2] ),
 +   ​quicksort2( Big, A2 - Z2).
 +
 +split( X, [], [], []).
 +
 +split( X, [Y|Tail], [Y|Small], Big)  :-
 +   gt( X, Y), !,
 +   ​split( X, Tail, Small, Big).
 +
 +split( X, [Y|Tail], Small, [Y|Big]) ​ :-
 +   ​split( X, Tail, Small, Big).
 +
 +gt(A,B):-A > B.
 +
 +%  conc(L1,​L2,​L3):​ list L3 is th econcatenation of lists L1 and L2
 +
 +conc( [], L, L).
 +
 +conc( [X | L1], L2, [X | L3])  :-
 +  conc( L1, L2, L3).</​code>​
 +===== Comments =====
  
pl/prolog/pllib/quicksort_2.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0