--- pl:prolog:pllib:quicksort_2 [2019/06/27 15:50]
+++ 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)

AIwiki

Menu