home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Power-Programmierung
/
CD1.mdf
/
prolog
/
library
/
diverses
/
sorts.pro
< prev
Wrap
Text File
|
1991-08-03
|
3KB
|
74 lines
/************************************************************************
* *
* 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(_,[],[],[]).