Implement this predicate in Prolog.
% hsort(In,Out):
% In is a list of structures, node(X,H), where X is a node label
% and H is h(X) the heuristic estimate assigned to X
% Out is the same as In after the nodes have been sorted
% in order by increasing H value.
% Implementation: use recursion and append. See insertion sort
% code in lecture notes for ideas.
% Test cases to demonstrate in screen shots:
% ?- hsort([ ], Sorted).
% Sorted = [ ].
% ?- hsort([node(a,3)], Sorted).
% Sorted = [node(a,3)].
% ?- hsort([node(b,1), node(a,3)], Sorted).
% Sorted = [node(b,1), node(a,3)].
% ?- hsort([node(a,3), node(b,1), node(c,4)], Sorted).
% Sorted= [node(b,1), node(a,3), node(c,4)].
% ?- hsort([node(d,5), node(c,4), node(a,1), node(b,2)], S).
% S= [node(a,1), node(b,2), node(c,4), node(d,5)].
hsort([],[]).
hsort([ node(A,B) | T],Sorted):- hsort(T,SortedTail),partition(B,SortedTail,L1,L2),append(L1,[node(A,B)|L2],Sorted).
partition(E,[],[],[]).
partition(E,[node(N,J)|T],[node(N,J)|T1],L2):-J<E,partition(E,T,T1,L2).
partition(E,[node(N,J)|T],L1,[node(N,J)|T2]):-J>=E,partition(E,T,L1,T2).
