sort.pro

来自「Prolog开发的简单的几个人工智能方面的程序.含问题分析报告.」· PRO 代码 · 共 44 行

domains
  ilist=integer*
predicates
  sort(ilist,ilist)
  split(ilist,ilist,ilist)
  split_on(integer,ilist,ilist,ilist)
  merge(ilist,ilist,ilist)
  length(integer,ilist)
clauses 
  sort([],[]):-!.
  sort([X],[X]):-!.
  sort([X1,X2|Y],Y):-
     split([X1,X2|_],Y1,Y2),
     sort(Y1,Z1),
     sort(Y2,Z2),!,
     merge(Z1,Z2,Y).
     
  merge([],X,X).
  merge(X,[],X).
  merge([B1|Y1],[B1|Y2],[B1,B1|Y]):-
     merge(Y1,Y2,Y).
  merge([B1|Y1],[B2|Y2],[B1|Y]):-
     B1<B2,
     merge(Y1,[B2|Y2],Y).
  merge([B1|Y1],[B2|Y2],[B2|Y]):-
     B2<B1,
     merge([B1|Y1],Y2,Y).      
     
  split(X,X1,X2):-
     length(N,X),    
     M=N/2,     
     split_on(M,X,X1,X2).
 split_on(0,X,[],X).
 split_on(Y,[X1|Z],[X1|Z1],Z2):-
     split_on(Y1,Z,Z1,Z2),
     Y=Y1+1.
 length(0,[]).
 length(M,[_|X]):-
    length(N,X),
    M=N+1.