1. insertion sort

1
2
3
4
5
6
7
8
9
10
11
let rec insertionSort lst =
match lst with
| [] -> []
| x :: nl -> insert x (insertionSort nl)
and insert ele ls =
match ls with
| [] -> []
| x :: nl -> if ele < x
then ele :: x :: nl
else x :: insert ele nl
;;

2. bubble sort (like c)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
let bubbleSort array = 
let len = Array.length array in
for i = 0 to len - 2 do
for j = 0 to len - 2 - i do
if (array.(j) > array.(j+1))
then
(
let tem = array.(j) in
array.(j) <- array.(j+1);
array.(j+1) <- tem;
)
done
done
;;

3. bubble sort (ML)

1
2
3
4
5
6
7
8
9
10
11
12
13
let rec swap list = 
match list with
| hd1::hd2::tl when hd1 > hd2 -> hd2 :: swap (hd1::tl)
| hd1::tl -> hd1 :: swap tl
| [] -> []
;;

let rec bubbleSortList lst =
let nl = swap lst in
if lst <> nl
then bubbleSortList nl
else lst
;;

The above implementation could be written as following:

1
2
3
4
5
6
7
8
9
10
let rec bubbleSortList list = 
let sorted = match list with
| hd1::hd2::tl when hd1 > hd2 ->hd2::soryList (hd1::tl)
| hd1::tl -> hd1::bubbleSortList tl
| tl -> tl
in
if list = sorted
then list
else bubbleSortList sorted
;;

4. merge sort

OCaml provides the sort module , the algorithm used in sort module is merging sort. Let us implement it by ourselves. The merge sort code in C++ is presented in sort list. We write it in OCaml which has the identical idea.

The first step, we need to have a merge function merging two sorted lists. The second function is the splitting which is used to split a list into two halves. In the version of C++, the list is split at the middle position while in this version, the new two half lists select elements from the original list one by one.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
(* merge two sorted lists *)
let rec merge (l1, l2) =
match (l1, l2) with
| [], [] -> []
| [], ls | ls, [] -> ls
| h1 :: t1, h2 :: t2 ->
if h1 <= h2 then
h1 :: (merge (t1, (h2::t2)))
else
h2 :: (merge ((h1::t1), t2))
;;


(* split a list into two same parts *)
let rec split lst =
match lst with
| [] -> [], []
| hd :: [] -> lst,[]
| hd :: tl ->
let t1, t2 = split tl in
hd :: t2, t1

(* main function *)
let rec mergeSort lst =
match lst with
| [] -> []
| hd :: [] -> lst
| ls ->
let l1, l2 = split ls in
merge(mergeSort l1, mergeSort l2)
;;


(* generate a random list of n integers between 0 and 100 *)
let rec random_list n =
let max = 100 in
if (n <= 0) then []
else (Random.int max)::random_list (n-1)
;;

let ls = random_list 10;;
let newls = mergeSort ls;;

let () = List.iter (printf "%d, ") newls; printf "\n";;

5. quick sort

Using OCaml to implement quick sort is very simple. List module provides partition function to split a list.

1
val partition : ('a -> bool) -> 'a list -> 'a list * 'a list

partition p l returns a pair of lists (l1, l2), where l1 is the list of all the elements of l that satisfy the predicate p, and l2 is the list of all the elements of l that do not satisfy p. The order of the elements in the input list is preserved.

We can also write this function by ourselves:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
let partition p l = 
let rec part left right lst =
match lst with
| [] -> ( left,right)
| hd :: nl ->
if p hd then part (hd::left) right nl
else part left (hd::right) nl in
part [] [] l
;;

let rec quickSort lst =
match lst with
| [] -> []
| pivot :: rest ->
let left, right = List.partition ((>) pivot) rest in
quickSort left @ pivot :: quickSort right
;;