Różnice między wybraną wersją a wersją aktualną.
| — |
pl:prolog:pllib:insertion_sort [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| + | ====== Insertion sort ====== | ||
| + | {{tag>sorting}} | ||
| + | ===== Description ===== | ||
| + | Learning insertion sort. | ||
| + | |||
| + | **Source**: PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7. | ||
| + | ===== Download ===== | ||
| + | Program source code: {{insertion_sort.pl}} | ||
| + | ===== Listing ===== | ||
| + | <code prolog> | ||
| + | % Figure 19.10 Learning insertion sort. | ||
| + | |||
| + | |||
| + | % Learning sort | ||
| + | |||
| + | backliteral( sort( L, S), [L:list], [S:list]). | ||
| + | backliteral( insert_sorted( X, L1, L2), [X:item, L1:list], [L2:list]). | ||
| + | |||
| + | term( list, [X | L], [X:item, L:list]). | ||
| + | term( list, [], []). | ||
| + | |||
| + | prolog_predicate( insert_sorted( X, L0, L)). | ||
| + | prolog_predicate( X=Y). | ||
| + | |||
| + | start_clause( [sort(L1,L2)] / [L1:list, L2:list] ). | ||
| + | |||
| + | ex( sort( [], [])). | ||
| + | ex( sort( [a], [a])). | ||
| + | ex( [ sort( [c,a,b], L), L = [a,b,c] ] ). % Uninstantiated 2nd arg. of sort! | ||
| + | ex( sort( [b,a,c], [a,b,c])). | ||
| + | ex( sort( [c,d,b,e,a], [a,b,c,d,e])). | ||
| + | ex( sort( [a,d,c,b], [a,b,c,d])). | ||
| + | |||
| + | nex( sort( [], [a])). | ||
| + | nex( sort( [a,b], [a])). | ||
| + | nex( sort( [a,c], [b,c])). | ||
| + | nex( sort( [b,a,d,c], [b,a,d,c])). | ||
| + | nex( sort( [a,c,b], [a,c,b])). | ||
| + | nex( sort( [], [b,c,d])). | ||
| + | |||
| + | insert_sorted( X, L, _) :- % Guarding clause: test instantiation of args. | ||
| + | var(X), !, fail | ||
| + | ; | ||
| + | var( L), !, fail | ||
| + | ; | ||
| + | L = [Y|_], var(Y), !, fail. | ||
| + | |||
| + | insert_sorted( X, [], [X]) :- !. | ||
| + | |||
| + | insert_sorted( X, [Y | L], [X,Y | L]) :- | ||
| + | X @< Y, !. % term X "lexicographically precedes" term Y | ||
| + | |||
| + | insert_sorted( X, [Y | L], [Y | L1]) :- | ||
| + | insert_sorted( X, L, L1). | ||
| + | </code> | ||
| + | ===== Comments ===== | ||
