-
Notifications
You must be signed in to change notification settings - Fork 0
/
sorting_things.ml
80 lines (70 loc) · 1.72 KB
/
sorting_things.ml
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
(* factorial : int -> int *)
let factorial n =
let rec factorial_inner n acc =
match n with
0 -> acc
| _ -> factorial_inner (n - 1) (acc * n)
in
factorial_inner n 1
(* insert : 'a -> 'a list -> 'a list *)
let rec insert x l =
match l with
[] -> [x]
| h :: t ->
if x < h
then x :: h :: t
else h :: insert x t
(* sort : 'a list -> 'a list *)
let rec insertion_sort l =
match l with
[] -> []
| h :: t -> insert h ( sort t)
(* merge : 'a list -> 'a list -> 'a list *)
let rec merge a b =
match (a, b) with
([], _) -> b
| (a, []) -> a
| (ha :: ta, hb :: tb) ->
if ha <= hb
then ha :: merge ta (hb :: tb)
else hb :: merge (ha :: ta) tb
(* merge_sort : 'a list -> 'a list *)
let rec merge_sort l =
match l with
[] -> []
| [x] -> [x]
| _ ->
let len = length l / 2 in
let (left, right) = (take len l, drop len l) in
merge (merge_sort left) (merge_sort right)
(* Exercises *)
(* insert : 'a -> 'a list -> 'a list *)
let rec insert x l =
match l with
[] -> [x]
| h :: t -> if x >= h then x :: h :: t else h :: insert x t
(* rev_sort : 'a list -> 'a list *)
let rec rev_sort l =
match l with
[] -> []
| h :: t -> insert h (rev_sort t)
(* is_sorted : 'a list -> bool *)
let rec is_sorted l =
match l with
[] | [_] -> true
| [x; y] -> x <= y
| x :: h :: t -> x <= h && is_sorted (h :: t)
(* single_sort : 'a list -> 'a list *)
let rec single_sort l =
let rec single_sort_insert x l =
match l with
[] -> [x]
| h :: t ->
if x <= h
then x :: h :: t
else h :: single_sort_insert x t
in
match l with
[] -> []
| [x] -> [x]
| h :: t -> single_sort_insert h (single_sort t)