Understanding this bubble sort solution in Prolog

Question

How does this bubble sort solution work in Prolog?

bubblesort([], []).
bubblesort([H], [H]).
bubblesort([H|D], R) :-
    bubblesort(D, E),
    [B|G] = E,
    (  (H =< B, R = [H|E])
    ;  (H > B,  bubblesort([B,H|G], R))
    ).

Here is an example trace: https://pastebin.com/T0DLsmAV

I understand the the line bubblesort(D,E), is responsible for sorting it down to one element, but I don't understand how this works. I understand the basics of lists in prolog, but still cannot work out how this solution operates.

Answer 1

note: the key to recursive problem solving is exactly not to think about the minutiae of our code's operations. Imagine you already have the solution, then just use it to solve a smaller subproblem, thus arriving at the full problem's solution.

---

Your code, with more suggestive variable names so I could follow it, reads:

bubblesort([], []).          % empty list is already sorted

bubblesort([H], [H]).        % singleton list is already sorted

bubblesort([H|T], S) :-      % `[H|T]` sorted is `S`,   *if*
    bubblesort(T, [M|R]),    %    `T` sorted is `[M|R]`,    *and*
    (                                 %   *either*,
       H =< M,                        %     in case `H` is not greater than `M`, 
             S = [H,M|R]              %       `S` is `[H,M|R]`,    
    ;                                 %   *or*
       H > M,                         %     in case `H` is greater than `M`,
             bubblesort([M,H|R], S)   %       `S` is `[M,H|R]` sorted by the same algorithm
    ).

(H is for "head", T is for "tail", S is "sorted", R "rest" and M is "minimum" -- see below for that).

We prove its correctness by structural induction. The induction hypothesis (IH) is that this definition is correct for shorter lists. We need to prove it is then also correct for a longer list. Indeed T is one-element shorter than [H|T]. Thus IH says [M|R] is sorted. This means M is the minimum element in T. It also means T is non-empty (sorting doesn't change the number of elements), so the clauses are indeed mutually-exclusive.

If H is not larger than the minimum element in T, [H,M|R] is obviously sorted.

Otherwise, we sort [M,H|R]. M is the minimum element and thus guaranteed to be the first in the result. What's actually sorted is [H|R], which is one element shorter, thus by IH sorting it works. QED.

If the last step sounds fishy to you, consider replacing the second alternative with the equivalent

    ;   H > M,                        %     in case `H` is greater then `M`,
             bubblesort([H|R], S1),   %       `S1` is `[H|R]` sorted by the same algorithm
                        S = [M|S1] 
    ).

where the applicability of the induction step is even clearer.

I'm not so sure it's a bubble sort though.

---

update: Indeed, measuring the empirical orders of growth, its number of inferences grows as ~ n³ (or slower), but true bubble sort clocked at ~ n^2.1 (close enough to the theoretical ~ n²), where n is the list's length:

tbs([], []).               % 'true' bubble sort
tbs([H],[H]).
tbs(L,S):- bubble(L,B),
           ( L==B -> S=L ; tbs(B,S) ).

bubble([],[]).
bubble([A],[A]).
bubble([A,B|C],R):- 
  (  A =< B -> bubble([B|C],X), R=[A|X]
  ;            bubble([A|C],X), R=[B|X] ).

Answer 2

The main difficulty with this code is that bad variable names were chosen and are making the logic harder to follow than it needs to be.

The first two cases are obviously base cases. The first says "the empty list is already sorted" and the second says "a singleton list is already sorted." This should make sense. The third case is where things get interesting.

Let's examine the first part.

bubblesort([H|D], R) :-
    bubblesort(D, E),

All that's happened so far is we've named our result R and broken our inputs into a first element H and a tail D. From there, we have said, let's bubblesort the tail of our input and call that E. Maybe this would be a little easier to follow?

bubblesort([H|T], Result) :-
    bubblesort(T, TSorted),

Next up,

    [B|G] = E,

Again, bad names, but what the author is intending to do here is straightforward: take apart the result of sorting the tail so we can talk about whether the next item in the sorted tail is the right element for that position, or if it needs to switch places with the head of our input. Let's rename:

    [HeadOfTSorted|RestOfTSorted] = TSorted,

Now we have a condition. Think of it in terms of prepending onto a sorted list. Say you have some element, like 3, and I hand you a sorted list. You want to determine if your 3 goes at the front or somewhere else. Well, suppose I gave you a sorted list that looked like [5,7,19,23,...]. You'd know that your 3 is right where it needs to be, and you'd hand back [3,5,7,19,23,...]. That's exactly the first case of the condition:

    (  (H =< HeadOfTSorted, Result = [H|TSorted])

Now consider another case, where I hand you a list that starts with [1,2,...]. You know you can't just put the three at the start and give me back [3,1,2,...]. But you don't really know where the 3 goes; it just doesn't go at the start. So what you have to do is resort the rest of the list with the 3 at the start, after the 1: [1 | resorted([3,2,...])]. That's effectively the other branch of the condition:

    ;  (H > HeadOfTSorted,  bubblesort([HeadOfTSorted,H|RestOfTSorted], R))
    ).

Hope this helps!