module sorting.
import lists.

% Permutation sort

type permutation  list A -> list A -> o.
type inorder      list int -> o.
type psort        list int -> list int -> o.

permutation nil nil.
permutation L (H::T) :-
  append V (H::U) L, append V U W, permutation W T.

inorder nil.
inorder (A::nil).
inorder (A::B::Rest) :- A =< B, inorder(B::Rest).

psort L1 L2 :- permutation L1 L2, inorder L2.

% Bubble sort
 
type bsort        list int -> list int -> o.

bsort L1 L2 :- 
  append Sorted (Big::Small::Rest) L1,
  Big > Small, !,
  append Sorted (Small::Big::Rest) BetterL1,
  bsort BetterL1 L2.
bsort L1 L1.

% Quick sort

type split        int -> list int -> list int -> list int -> o.
type qsort        list int -> list int -> o.

split X nil nil nil.
split X (A::Rest) (A::S) B :- A =< X, split X Rest S B.
split X (A::Rest) S (A::B) :- A > X,  split X Rest S B.

qsort nil nil.
qsort (First::Rest) Sorted :-
  split First Rest Small Big,
  qsort Small SmallSorted,
  qsort Big BigSorted,
  append SmallSorted (First::BigSorted) Sorted.