### Sorting Algorithms

#### Bubble Sort

Please don't use this one!

```domains
int  = integer
ints = int*
predicates
bubble_sort(ints,ints)
append(ints,ints,ints)
clauses

/* bubble_sort(Xs, Ys) is true if Ys is a sorted permutation of the        */
/*   list Xs.                                                              */
bubble_sort(Xs, Ys):-
append(Ws, [A,B|Zs], Xs),
B < A,
append(Ws, [B,A|Zs], Vs),
bubble_sort(Vs, Ys), !.
bubble_sort(Xs, Xs).

/* append(Xs, Ys, Zs) is true if Zs is the result of appending the list Xs */
/*   to the list Ys.                                                       */
append([], Ys, Ys).
append([X|Xs], Ys, [X|Zs]):-append(Xs, Ys, Zs).
```

#### Selection Sort

And don't use this one either!

```domains
int  = integer
ints = int*
predicates
seln_sort(ints,ints)
minimum(ints,int,int)
efface(ints,int,ints)
clauses

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

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

/* efface(Xs, Y, Zs) is true if Zs is the result of deleting the first     */
/*   occurrence of the element Y from the list Xs.                         */
efface([Y|Xs], Y, Xs):-!.
efface([X|Xs], Y, [X|Zs]):-efface(Xs, Y, Zs).
```

#### 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 is left as an exercise for the reader!

```domains
int  = integer
ints = int*
heap = heap(int,heap,heap) ; void
predicates
heap_sort(ints,ints)
list_heap(ints,heap)
list_heap_1(ints,heap,heap)
heap_list(heap,ints)
insert_heap(int,heap,heap)
remove_heap(int,heap,heap)
remove_heap_1(int,heap,heap)
heap(heap,heap)
clauses

/* 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([X|Xs], Heap0, Heap):-
insert_heap(X, Heap0, Heap1),
list_heap_1(Xs, Heap1, Heap).
list_heap_1([], Heap, 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), heap(Top, Right, Left1)):-
Value < Top, !,
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)),
heap(LeftValue, Left, heap(RightValue, RightLeft, RightRight))):-
RightValue < LeftValue, Top < LeftValue, !,
heap(heap(Top, LeftLeft, LeftRight), Left).
heap(heap(Top, Left, heap(RightValue, RightLeft, RightRight)),
heap(RightValue, Left, Right)):-
Top < RightValue, !,
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.

```domains
int  = integer
ints = int*
predicates
insertion_sort(ints,ints)
insertion_sort_1(ints,ints,ints)
insert(ints,int,ints)
clauses

/* 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, [Y|Zs]):-Y < X, !, insert(Ys, X, Zs).
insert(Ys, X, [X|Ys]).
```

#### Quicksort

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

```domains
int  = integer
ints = int*
predicates
quicksort(ints,ints)
quicksort_1(ints,ints,ints)
partition(ints,int,ints,ints)
clauses

/* 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([K|L], X, M, [K|N]):-
X < K, !,
partition(L, X, M, N).
partition([K|L], X, [K|M], N):-
partition(L, X, M, N).
partition([], _, [], []).
```

#### Tree Sort

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

```domains
int  = integer
ints = int*
tree = tree(int,tree,tree) ; void
predicates
tree_sort(ints,ints)
make_tree(ints,tree,tree)
in_order_dl(tree,ints,ints)
insert_tree(int,tree,tree)
clauses

/* 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), tree(X,L,R)):-!.
insert_tree(X, tree(Y,L,R), tree(Y,L1,R)):-
X < Y, !, 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(tree(X,L,R), Xs, Zs):-
in_order_dl(R, Ys, Zs),
in_order_dl(L, Xs, [X|Ys]).
in_order_dl(void, Xs, Xs).
```

#### Merge Sort

This is, in general, the best sorting algorithm.

```domains
int  = integer
ints = int*
predicates
merge_sort(ints,ints)
merge_sort_1(int,ints,ints,ints)
ordered_merge(ints,ints,ints)
length(ints,int)
length_1(ints,int,int)
clauses

/* 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, Ys, Zs) 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], [A], Rest):-!.
merge_sort_1(2, [A,B|Rest], C, Rest):-A <= B, !, C = [A,B].
merge_sort_1(2, [A,B|Rest], C, Rest):-/* A > B, */ !, C = [B,A].
merge_sort_1(N, List, Sorted, Rest):-
N1 = N div 2, N2 = N - N1,
merge_sort_1(N1, List, SortedLeft, TempList),
merge_sort_1(N2, TempList, SortedRight, Rest),
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([X|Xs], [Y|Ys], [Y|Zs]):-
Y <= X, !,
ordered_merge([X|Xs], Ys, Zs).
ordered_merge([X|Xs], Ys, [X|Zs]):-
ordered_merge(Xs, Ys, Zs).
ordered_merge([], Ys, Ys).

/* length(Xs, L) is true if L is the number of elements in the list Xs.    */
length(Xs, L):-length_1(Xs, 0, L).

/* length_1(Xs, L0, L) is true if L is equal to L0 plus the number of      */
/*   elements in the list Xs.                                              */
length_1([], L, L).
length_1([_|Xs], L0, L):-L1 = L0 + 1, length_1(Xs, L1, L).
```