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).

Sort Index     Turbo Prolog Index     Home Page

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).

Sort Index     Turbo Prolog Index     Home Page

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).

Sort Index     Turbo Prolog Index     Home Page

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]).

Sort Index     Turbo Prolog Index     Home Page

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([], _, [], []).

Sort Index     Turbo Prolog Index     Home Page

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).

Sort Index     Turbo Prolog Index     Home Page

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).

Sort Index     Turbo Prolog Index     Home Page