How to write gnom sort in prolog?-CodePudding

It's my first time with Prolog programming and I have issues with gnome sort, I've read it's similar to insert and bubble sort, but I have no idea how to connect them.

gnome_sort(List,Sorted):-g_sort(List,[],Sorted). 

g_sort([],Acc,Acc). 
g_sort([H|T],Acc,Sorted):-insert(H,Acc,NAcc),g_sort(T,NAcc,Sorted). 


last_element(X,[X]).
last_element(X,[_|O]):-last_element(X,O).
   
insert(X, last_element(P,[Y|T]),[Y|NT]):-X>P,g_sort(Y,P,NT). 
insert(X,[Y|T],[X,Y|T]):-X=<Y.
insert(X,[],[X]).

I have something like this but it doesn't work :((((((((

CodePudding user response：

Note that what you're implementing is not the real Gnome sort but rather something more like the "optimization" noted on the Wikipedia page which is a completely different algorithm that is an insertion sort and has nothing to do with Gnome sort itself.

Anyway, your general approach works, but your implementation of insert/3 is broken. This is a predicate that should only insert an element into a list that is already assumed to be sorted. This predicate should never refer to g_sort: You don't want to freshly sort a list, only insert one element. You also don't need to refer to refer to the list's last element.

The only choice that insert/3 needs to make in a given situation is: is X greater than the first element of the sorted list or not? You already handle two cases correctly: Where the list is empty, and where X =< Y.

Only one clause of your insert/3 needs to change:

insert(X, [Y | Ys], [Y | XYs]) :-
    X > Y,
    insert(X, Ys, XYs).

If X > Y, this "skips" Y and looks for the correct insertion position in the rest of the list.

For comparison, your clause looked like this:

insert(X, last_element(P,[Y|T]),[Y|NT]):-X>P,g_sort(Y,P,NT).

I'm not sure what you were trying to do here, maybe you were going for a "function call" to last_element? Remember that Prolog has no function calls. If you write something like last_element(A, B) in a clause head, that refers to a term of the shape last_element(A, B), not to a "result" of "evaluating" the term last_element(A, B).

(Also, do you see how I put each goal on a separate line and used spaces around operators and after commas? You should do that too. Prolog is already hard enough to read when it's nicely formatted, you shouldn't make it even harder with bad formatting.)

For whatever it's worth, a real Gnome sort in Prolog would look like this:

gnomesort(List, Sorted) :-
    gnomesort([], List, Sorted).

gnomesort(Left, [], Sorted) :-
    reverse(Left, Sorted).
gnomesort([], [R | Rs], Sorted) :-
    gnomesort([R], Rs, Sorted). 
gnomesort([L | Ls], [R | Rs], Sorted) :-
    R @>= L, 
    gnomesort([R, L | Ls], Rs, Sorted).
gnomesort([L | Ls], [R | Rs], Sorted) :-
    R @< L,
    gnomesort(Ls, [R, L | Rs], Sorted).

CodePudding user response：

I know my code doesn't work properly, but do you know how could I stop my program when X>=P is't correct? last_element(X,[X]). last_element(X,[_|O]):-last_element(X,O).

insert(X,[Y|T],[X,Y|T]):-last_element(P,[Y|T]),X>=P.

Because when X>=P is not corect he goes back to the last_element functio.