A Quick Sort implementation written in Prolog.

% Varesano Fabio - QuickSort

/* [+,-] */
quicksort([], []).
quicksort([HEAD | TAIL], SORTED) :- partition(HEAD, TAIL, LEFT, RIGHT),
                                    quicksort(LEFT, SORTEDL),
                                    quicksort(RIGHT, SORTEDR),
                                    append(SORTEDL, [HEAD | SORTEDR], SORTED).

/* [+,+,-,-] */
partition(PIVOT, [], [], []).
partition(PIVOT, [HEAD | TAIL], [HEAD | LEFT], RIGHT) :- HEAD @=< PIVOT,
                                                         partition(PIVOT, TAIL, LEFT, RIGHT).
partition(PIVOT, [HEAD | TAIL], LEFT, [HEAD | RIGHT]) :- HEAD @> PIVOT,
                                                         partition(PIVOT, TAIL, LEFT, RIGHT).

/* [+,+,-] */
append([], LIST, LIST).
append([HEAD | LIST1], LIST2, [HEAD | LIST3]) :- append(LIST1, LIST2, LIST3).

This is a simple implementation of the Odd/Even Quick Sort Algorithm in OCAML.

This algorithm orders even numbers before the odds numbers. Eg: given the numbers 6,3,1,2,4,5 it will return 2,4,6,1,3,5

(*
Fabio Varesano - 2007/05/11
Quick sort Odd-even

final order will be:
as example: 2,4,6,1,3,7
*)


let leq a b = if ( (a mod 2==0 && b mod 2==1) || ((a mod 2==0 && b mod 2==0) && a<=b) || ((a mod 2==1 && b mod 2==1) && a<=b)) then true else false;;

let rec quicksort leq list =
  match list with
  | [] -> []
  | [x] -> [x]
  | pivot::rest ->
      let rec partition left right list =
        match list with
        | [] -> quicksort leq left @ (pivot :: quicksort leq right)
        | head::tail -> if leq head pivot then partition (head::left) right tail
                                         else partition left (head::right) tail
      in partition [] [] rest;;


quicksort leq [3;4;6;1;9;20;5;7;4;2;8];;