### Sorting Algorithms

#### Bubble Sort

```/* bubble_sort(Xs, Ys) is true if Ys is a sorted permutation of the        */
/*   list Xs.                                                              */
bubble_sort(Xs, Ys):-
bubble_sort_1(Xs, [], Ys).

bubble_sort_1([], Ys, Ys).
bubble_sort_1([X|Xs], Ys0, Ys):-
bubble(Xs, X, Xs1, Y),
bubble_sort_1(Xs1, [Y|Ys0], Ys).

bubble([], A, [], A).
bubble([B|Xs], A, [B|Xs1], Y):-A > B, !, bubble(Xs, A, Xs1, Y).
bubble([B|Xs], A, [A|Xs1], Y):-bubble(Xs, B, Xs1, Y).
```

#### Selection Sort

And don't use this one either!

```/* seln_sort(Xs, Ys) is true if Ys is a sorted permutation of the list Xs. */
seln_sort([], []).
seln_sort([X|Xs], [Y|Ys]):-
minimum(Xs, X, Y),
remove(Y, [X|Xs], Zs), !,
seln_sort(Zs, Ys).

/* minimum(Xs, X, Min) is true if Min is the smallest element in the       */
/*   list [X|Xs].                                                          */
minimum([], X, X).
minimum([Y|Ys], X, Z):-
Y =< X, !,
minimum(Ys, Y, Z).
minimum([_|Ys], X, Z):-
minimum(Ys, X, Z).
```

#### Heap Sort

This is pretty slow as well, but demonstrates the implementation of a heap in Prolog, borrowed from D. Poole and M. Horsch. This algorithm sorts the elements in descending order of sequence, contrary to the other algorithms given here. The changes required to sort in ascending order are left as an exercise for the reader!

```/* heap_sort(Xs, Ys) is true if Ys is a sorted permutation of the list Xs. */
heap_sort(List, SortedList):-
list_heap(List, Heap),
heap_list(Heap, SortedList).

/* list_heap(List, Heap) is true if Heap is the result of inserting        */
/*   successive elements of the List into an empty heap.                   */
list_heap(List, Heap):-list_heap_1(List, void, Heap).

list_heap_1([], Heap, Heap).
list_heap_1([X|Xs], Heap0, Heap):-
insert_heap(X, Heap0, Heap1),
list_heap_1(Xs, Heap1, Heap).

/* heap_list(Heap, List) is true if List is the result of removing         */
/*   successive elements from the Heap.                                    */
heap_list(void, []):-!.
heap_list(Heap, [X|Xs]):-
remove_heap(X, Heap, Heap1),
heap_list(Heap1, Xs).

/* insert_heap(Value, Heap1, Heap2) is true if inserting Value into Heap1  */
/*   gives Heap2.                                                          */
insert_heap(Value, heap(Top, Left, Right), NewHeap):-
Value < Top, !,
NewHeap = heap(Top, Right, Left1),
insert_heap(Value, Left, Left1).
insert_heap(Value, heap(Top, Left, Right), heap(Value, Right, Left1)):-
!,
insert_heap(Top, Left, Left1).
insert_heap(Value, void, heap(Value, void, void)).

/* remove_heap(Top, Heap1, Heap2) is true if removing Top from Heap1       */
/*   gives Heap2.                                                          */
remove_heap(Top, heap(Top, void, Right), Right):-!.
remove_heap(Top, heap(Top, Left, Right), NewHeap):-
remove_heap_1(Value1, Right, Right1),
heap(heap(Value1, Right1, Left), NewHeap).

remove_heap_1(Top, heap(Top, void, Right), Right):-!.
remove_heap_1(Value, heap(Top, Left, Right), heap(Top, Left1, Left)):-
remove_heap_1(Value, Right, Left1).

/* heap(Heap1, Heap2) is true if Heap2 is the heap derived from the        */
/*   pseudo-heap Heap1.                                                    */
heap(heap(Top, heap(LeftValue, LeftLeft, LeftRight),
heap(RightValue, RightLeft, RightRight)), NewHeap):-
RightValue < LeftValue, Top < LeftValue, !,
NewHeap = heap(LeftValue, Left, heap(RightValue, RightLeft, RightRight)),
heap(heap(Top, LeftLeft, LeftRight), Left).
heap(heap(Top, Left, heap(RightValue, RightLeft, RightRight)), NewHeap):-
Top < RightValue, !,
NewHeap = heap(RightValue, Left, Right),
heap(heap(Top, RightLeft, RightRight), Right).
heap(Heap, Heap).
```

#### Insertion Sort

This is the simplest sort, but is a bit slow when sorting lots of data.

```/* insertion_sort(Xs, Zs) is true if Zs is a sorted permutation of the     */
/*   list Xs.                                                              */
insertion_sort(Xs, Ys):-insertion_sort_1(Xs, [], Ys).

insertion_sort_1([], Ys, Ys).
insertion_sort_1([X|Xs], Ys0, Ys):-
insert(Ys0, X, Ys1),
insertion_sort_1(Xs, Ys1, Ys).

insert([Y|Ys], X, Ws):-Y < X, !, Ws = [Y|Zs], insert(Ys, X, Zs).
insert(Ys, X, [X|Ys]).
```

#### Quicksort

This is the classic sort algorithm, but its worst case performance is not good.

```/* quicksort(Xs, Ys) is true if Ys is a sorted permutation of the list Xs. */
quicksort(Xs, Ys):-quicksort_1(Xs, Ys, []).

quicksort_1([], Ys, Ys).
quicksort_1([X|Xs], Ys, Zs):-
partition(Xs, X, Ms, Ns),
quicksort_1(Ns, Ws, Zs),
quicksort_1(Ms, Ys, [X|Ws]).

/* partition(Ls, X, Ms, Ns) is true if the list Ms contains the elements   */
/*   of the list Ls which are less than or equal to X, and the list Ns     */
/*   contains the elements of Ls which are greater than X.                 */
partition([], _, [], []).
partition([K|Ls], X, Ms, Ps):-
X < K, !, Ps = [K|Ns], partition(Ls, X, Ms, Ns).
partition([K|Ls], X, [K|Ms], Ns):-
partition(Ls, X, Ms, Ns).
```

#### Tree Sort

This has a similar worst case performance as Quicksort. Repeated elements will not appear in the sorted list.

```/* tree_sort(Xs, Ys) is true if Ys is a sorted permutation of the list Xs. */
tree_sort(Xs, Ys):-
make_tree(Xs, void, T),
in_order_dl(T, Ys, []).

/* make_tree(List, Tree, NewTree) is true if NewTree is the binary tree    */
/*   resulting from inserting the elements of the List into the binary     */
/*   tree Tree.                                                            */
make_tree([], T, T).
make_tree([X|Xs], T, U):-
insert_tree(X, T, V),
make_tree(Xs, V, U).

/* insert_tree(X, Tree, NewTree) is true if NewTree is the result of       */
/*   inserting the element X as a leaf in the ordered binary tree Tree.    */
/*   If the element X is already in the tree, the tree is unchanged.       */
insert_tree(X, tree(X,L,R), Z):-
!, Z = tree(X,L,R).
insert_tree(X, tree(Y,L,R), Z):-
X < Y, !, Z = tree(Y,L1,R), insert_tree(X, L, L1).
insert_tree(X, tree(Y,L,R), tree(Y,L,R1)):-
!,
insert_tree(X, R, R1).
insert_tree(X, void, tree(X,void,void)).

/* in_order_dl(Tree, Ls, Ms) is true if the difference list Ls, Ms is an   */
/*   in-order traversal of the binary tree Tree.                           */
in_order_dl(void, Xs, Xs).
in_order_dl(tree(X,L,R), Xs, Zs):-
in_order_dl(R, Ys, Zs),
in_order_dl(L, Xs, [X|Ys]).
```

#### Merge Sort

This is, in general, the best sorting algorithm.

```/* merge_sort(Xs, Ys) is true if Ys is a sorted permutation of the list Xs.*/
merge_sort(List, SortedList):-
length(List, Length),
merge_sort_1(Length, List, [], SortedList).

/* merge_sort_1(N, Xs, Zs, Ys) is true if Ys is a sorted permutation of    */
/*  the first N elements of the list Xs, and Zs are the remaining elements */
/*  of Xs.                                                                 */
merge_sort_1(0, Rest, Rest, []):-!.
merge_sort_1(1, [A|Rest], Rest, [A]):-!.
merge_sort_1(N, List, Rest, Sorted):-
N1 is N // 2,
N2 is N - N1,
merge_sort_1(N1, List, TempList, SortedLeft),
merge_sort_1(N2, TempList, Rest, SortedRight),
ordered_merge(SortedLeft, SortedRight, Sorted).

/* ordered_merge(Xs, Ys, Zs) is true if Zs is an ordered list obtained     */
/*   from merging the ordered lists Xs and Ys.                             */
ordered_merge([], Ys, Ys).
ordered_merge([X|Xs], [Y|Ys], Ws):-
Y =< X, !, Ws = [Y|Zs], ordered_merge([X|Xs], Ys, Zs).
ordered_merge([X|Xs], Ys, [X|Zs]):-
ordered_merge(Xs, Ys, Zs).
```