sort.pl

PRl教学程序 PRl教学程序 PRl教学程序

/********************************************************************
    Constraint-based Graphical Programming in B-Prolog
    %
    animate the bubble sort algorithm
*********************************************************************/
go:-
    sort(15).

sort(N):-
    length(L,N),
    randoms(L),
    cgStartRecordAnimation(sort),
    bubble_sort([],L),
    cgStopRecord.

randoms([]).
randoms([X|Xs]):-
    random(X),
    randoms(Xs).

bubble_sort(Sorted,[]).
bubble_sort(SortedL,L):-
    select_min(L,X),
    append(Left,[X|Right],L),
    not(not(visualize(SortedL,Left,X,Right))),
    append(SortedL,[X],SortedL1),
    (Left=[Cur|Left1]->append(Left1,[Cur|Right],Rest);
     Rest=Right),
    bubble_sort(SortedL1,Rest).

select_min([X|L],Min):-
    select_min(L,X,Min).

select_min([],Min0,Min):-Min=Min0.
select_min([X|Xs],Min0,Min):-
    (X<Min0 -> 
     select_min(Xs,X,Min);
     select_min(Xs,Min0,Min)).
    
visualize(Sorted,[Cur|Left],Min,Right):-
    numbers2rectLabels(Sorted,SortedLabs,SortedRects),
    numbers2rectLabels(Left,LeftLabs,LeftRects),
    numbers2rectLabels(Right,RightLabs,RightRects),
    number2rectLabel(Cur,CurLab,CurRect),CurRect^color #= red,
    number2rectLabel(Min,MinLab,MinRect),MinRect^color #= blue,
    %
    append(SortedLabs,[CurLab|LeftLabs],[MinLab|RightLabs],Labs),
    append(SortedRects,[CurRect|LeftRects],[MinRect|RightRects],Rects),
    visualize(Labs,Rects).
visualize(Sorted,[],Min,Right):-
    numbers2rectLabels(Sorted,SortedLabs,SortedRects),
    numbers2rectLabels(Right,RightLabs,RightRects),
    number2rectLabel(Min,MinLab,MinRect),MinRect^color #= red,
    %
    append(SortedLabs,[MinLab|RightLabs],Labs),
    append(SortedRects,[MinRect|RightRects],Rects),
    visualize(Labs,Rects).

visualize(Labs,Rects):-
    cgSameColumnWithPad(Labs,10),
    cgSame(Labs,x),  cgSame(Rects,x), 
    %
    cgDefaultWindow(W),
    W^leftMargin #= 100, W^topMargin #= 100,
    append(Labs,Rects,Os),
    cgPack(Os),
    cgCleanDefaultWindow,
    cgShow(Os),
    cgSleep(1000).
    
numbers2rectLabels([],Labs,Rs):-Labs=[],Rs=[].
numbers2rectLabels([X|Xs],Labs,Rs):-
    Labs=[Lab|Labs1],
    Rs=[R|Rs1],
    number2rectLabel(X,Lab,R),
    numbers2rectLabels(Xs,Labs1,Rs1).

number2rectLabel(X,Lab,R):-
    cgRectangle(Box),
    cgLabel(Lab), Lab^text #= X, cgInside(Lab,Box),
    cgSame([Box,Lab],centerY),
    Width is round(X*200),
    cgRectangle(R), R^width #= Width, R^height #<10,
    cgTable([[Box,R]]).
    
cgSameColumnWithPad([Lab1,Lab2|Labs],Pad):-!,
    Lab2^y #= Lab1^y+Pad,
    cgSameColumnWithPad([Lab2|Labs],Pad).
cgSameColumnWithPad(_,Pad).

append(L1,L2,L3,L4):-
    append(L2,L3,L23),
    append(L1,L23,L4).