CODEWITHSUNDEEP
prologappendbubble-sort
Indrajith
Indrajith

Reputation: 11

Need explanation on this SWI Prolog bubble sort coding

Need to know what are these L1, [H1 | L2]. No idea at all.

bubSort([],[]) :- !.
bubSort([H],[H]) :- !.
bubSort(L,SL) :- append(L1, [H1,H2|L2], L), H2 < H1, append(L1, [H2,H1|L2], NL), !,
                 bubSort(NL,SL).
bubSort(L,L).

This compiles and sorts the list well. But I need to understand this mechanism. Specially the how this append works.

Upvotes: 0

Views: 504

Answers (1)

Will Ness
Will Ness

Reputation: 71099

  • L1 : a logical variable (the name suggestive of a "list")
  • L1 = [H1 | L2] : the list L1 has H1 as its head element, and L2 is a list of all the rest of its elements
  • append(L1, [H1,H2|L2], L) : the list L consists of the elements of a list L1, then the element H1, then the element H2, and the elements of the list L2 after that
  • H2 < H1 : an arithmetical value referred to by the logical variable H2 is smaller in magnitude than the arithmetical value referred to by the logical variable H1
  • append(L1, [H2,H1|L2], NL) : the list NL consists of the elements of a list L1, then the element H2, then the element H1, and the elements of the list L2 after that
  • bubSort([],[]) :- !. bubSort of an empty list [] is an empty list, []
  • bubSort([H],[H]) :- !. bubSort of a singleton list [H] (a list with just one element, H, in it) is a singleton list [H], i.e. the same list
  • bubSort(L,SL) :- append(L1, [H1,H2|L2], L), H2 < H1, append(L1, [H2,H1|L2], NL), !, bubSort(NL,SL). : bubSort of a list, call it L, is a list, call it SL (for "sorted list"), such that there exist two adjacent elements in L which are out of order, the list NL is exactly the same as L just with those two adjacent elements swapped, and the bubSort of NL is SL
  • bubSort(L,L). : finally, if there's no two adjacent elements which are out of order, bubSort of such list is the list itself.

see also: How do I append lists in prolog?

Upvotes: 1

Related Questions