# Różnice

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

 — 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 ===== + + % 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).​ + ===== Comments =====
pl/prolog/pllib/quicksort_2.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)