home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / prolog / pdprolog / sort.pro < prev    next >
Text File  |  1986-05-05  |  2KB  |  87 lines
  1.                        /* Sorting Lists */
  2.  
  3. /*
  4. The order predicate determines how you would like the list to be ordered:
  5. */
  6.  
  7. order( A, B ) :- A > B.
  8.  
  9. /* The bubble sort. Invoke as ?-busort( [1,2,3], Sortlist ).
  10. The answer is instantiated as the sorted list. */
  11.  
  12. busort( L, S ) :-
  13.     append( X, [A, B|Y], L ),
  14.     order( A, B ),
  15.     append( X, [B,A|Y], M ),
  16.     busort( M, S ).
  17. busort( L, L ).
  18.  
  19. /* Used by most sorting algorithms. */
  20. append( [], L, L ).
  21. append( [H|T], L, [H|V] ) :- append( T, L, V ).
  22.  
  23.  
  24. /* The quick sort. */
  25.  
  26.  
  27. quisort( [H|T], S ) :-
  28.     split( H, T, A, B ),
  29.     quisort( A, A1 ),
  30.     quisort( B, B1 ),
  31.     append( A1, [H|B1], S ).
  32.  
  33. /* This important clause was left out by Clocksin and Mellish: */
  34. quisort( [], [] ).
  35.  
  36. /* List splitting predicates used by both quick sort algorithms: */
  37.  
  38. split( H, [A|X], [A|Y], Z ) :- order( A, H ), split( H, X, Y, Z ).
  39. split( H, [A|X], Y, [A|Z] ) :- order( H, A ), split( H, X, Y, Z ).
  40. split( _, [], [], [] ).
  41.  
  42.  
  43. /* 
  44. A compact form of the quick sort. 
  45. Invoke as: ?-quisort( List, Sortlist, [] ).
  46. */
  47.  
  48. quisortx( [H|T], S, X ) :-
  49.     split( H, T, A, B ), 
  50.     quisortx( A, S, [H|Y] ),
  51.     quisortx( B, Y, X ).
  52. quisortx( [], X, X ).
  53.  
  54.  
  55. /*
  56. The insertion sort:
  57. Invoke as ?-insort( List, Sortlist ).
  58. */
  59. insort( [], [] ).
  60. insort( [X|L], M ) :- insort( L, N ), insortx( X, N, M ).
  61.  
  62. insortx( X, [A|L], [A|M] ) :- order( A, X ), !, insortx( X, L, M ).
  63. insortx( X, L, [X|L] ).
  64.  
  65.  
  66. insort( [], [], _ ).
  67. insort( [X|L], M, O ) :- insort( L, N, O ), insortx( X, N, M, O ).
  68.  
  69.  
  70. /* 
  71. This form of the insertion sort needs no sort parameter.
  72. O is instantiated to a predicate or operator which orders the elements.
  73. Invoke as: insort( List, Sortlist, <order> ).
  74. For instance, ?-insort( List, Sortlist, < ).
  75. */
  76.  
  77. insortb( [], [], _).
  78. insortb( [X|L], M, O ) :- insortb( L, N, O ), insortxb( X, N, M, O ).
  79.  
  80.  
  81. insortxb( X, [A|L], [A|M], O ) :-
  82.     P =.. [ O, A, X ],
  83.     P,
  84.     !,
  85.     insortxb( X, L, M, O ).
  86. insortxb( X, L, [X|L], O ).
  87.