/************************************************************************
 *                                                                      *
 *  These are the insertion sort, bubble sort, and quick sort algos     *
 *  from C&M implemented for Turbo Prolog.  The functions are only      *
 *  defined here for lists of symbols, but can handle other list types  *
 *  by adding to the predicate declarations.                            *
 *                                                                      *
 *  Compiled by John Reece                                              *
 *                                                                      *
 ************************************************************************/
 
domains
   list = symbol*
  
predicates
   append(list,list,list)         /* Needed by bubble sort and quick sort */
   order(symbol,symbol)           /* Succeeds if the first and second parameters are 
                                     are in the desired order - here in ascending order  */
   insertsort(list,list)          /* Insertion sort */
   insortx(symbol,list,list)      /* Needed by insertion sort */
   bubblesort(list,list)          /* Bubble sort */
   quicksort(list,list)           /* Quick sort */
   split(symbol,list,list,list)   /* Needed by quick sort */

clauses

/***** used by bubblesort() and quicksort() *****/

append([],L,L).
append([H|T],L,[H|V]) if
      append(T,L,V).

/****** order(A,B) succeeds if the predicates are in the desired order.  This is
        not necessarily a trivial definition in comparing certain domain types.  ******/
      
order(A,B) if
   A < B.

/****** The insertion sort method, what else? ******/ 
   
insertsort([],[]).
insertsort([X|L],M) if
      insertsort(L,N) and
      insortx(X,N,M).
insortx(X,[A|L],[A|M]) if
      order(A,X) and
      ! and
      insortx(X,L,M).
insortx(X,L,[X|L]).

/***** bubble sort method *****/

bubblesort(L,S) if
      append(X,[A,B|Y],L) and
      
      order(B,A) and
      append(X,[B,A|Y],M) and
      bubblesort(M,S) and
      !.
bubblesort(L,L).
      
/***** the quick sort method - the best if the list is totally out of order *****/

quicksort([],[]).
quicksort([H|T],S) if
       split(H,T,A,B) and
       quicksort(A,A1) and
       quicksort(B,B1) and
       append(A1,[H|B1],S).
split(H,[A|X],[A|Y],Z) if A <= H and split(H,X,Y,Z).
split(H,[A|X],Y,[A|Z]) if A > H and split(H,X,Y,Z).
split(_,[],[],[]).