为何bubblesort([8,7,6,5,4,3,2,1],L)返回未排序列表？

Let's break down what's going wrong with your code, and how to fix it.

The Core Issues #

Your implementation has two critical flaws that prevent it from sorting correctly:

1. swap/2 only performs a single swap, not a full bubble pass
   Bubblesort relies on repeatedly traversing the entire list to swap adjacent out-of-order pairs, which pushes the largest unsorted element to its correct position at the end of the list each pass. But your swap/2 stops after finding the first possible swap. For example, given [8,7,6,5,...], it swaps 8 and 7 to get [7,8,6,5,...] and returns immediately—no further swaps happen in that "pass".

2. The cut (!) blocks necessary backtracking
   In your first bubblesort/2 clause, the ! after swap(inputList, List) tells Prolog not to backtrack. This means once a single swap is done, Prolog won't attempt any more swaps in the same pass—it jumps straight to recursing with the partially swapped list. This ensures you never complete a full bubble pass, so elements never get pushed all the way to their correct positions.

Let's Walk Through Your Code's Execution #

When you run bubblesort([8,7,6,5,4,3,2,1], L):

• First swap: 8 and 7 → [7,8,6,5,4,3,2,1] (the cut blocks any further swaps here)
• Recurse with this new list: swap 8 and 6 → [7,6,8,5,4,3,2,1] (cut again)
• Recurse: swap 7 and 6 → [6,7,8,5,4,3,2,1]
• Recurse: swap 8 and 5 → [6,7,5,8,4,3,2,1]
• This pattern continues, swapping one pair per recursive call, but never finishing a full pass to push the largest element to the end. The list never gets fully sorted.

Fixed Implementation #

To fix this, we need to modify the code to perform full bubble passes instead of single swaps. Here's a corrected version:

% Perform one full bubble pass: pushes the largest unsorted element to the end
bubble([], []).
bubble([X], [X]).
bubble([X,Y|Rest], [X|Rest1]) :- 
    X =< Y, 
    bubble([Y|Rest], Rest1).
bubble([X,Y|Rest], [Y|Rest1]) :- 
    X > Y, 
    bubble([X|Rest], Rest1).

% Bubblesort: keep doing passes until no more swaps are needed
bubblesort(List, Sorted) :-
    bubble(List, Temp),
    Temp \= List,  % Check if any swaps happened
    !,
    bubblesort(Temp, Sorted).
bubblesort(List, List).  % Base case: list is already sorted

% Helper to print lists (unchanged)
printlist([]) :- nl.
printlist([Head|List]) :- write(Head), write(" "), printlist(List).

How This Works #

• bubble/2 traverses the entire list, swapping adjacent out-of-order pairs as it goes. By the end of the call, the largest element in the unsorted portion is at the end of the list.
• The bubblesort/2 clause checks if the bubbled list is different from the original (meaning swaps happened). If so, it recurses with the new list. If not, the list is sorted, and we hit the base case.

Now when you run bubblesort([8,7,6,5,4,3,2,1], L), you'll get L = [1,2,3,4,5,6,7,8] as expected.

内容的提问来源于stack exchange，提问作者Ashik