-
Notifications
You must be signed in to change notification settings - Fork 0
/
Practica5.txt
156 lines (102 loc) · 4.27 KB
/
Practica5.txt
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
********PRACTICA 5 PROGRAMACION DECLARATIVA********
**** Jesús Ángel Pérez-Roca Fernández (infjpf02) ****
*****************************************************
DEFINIR LAS SIGUIENTES FUNCIONES
FUNCION FUNCION EQUIVALENTE
insert_sort let rec insert_sort l=match l with
[]->[]
|h::t->let rec aux x l=match l with
[]->[x]
|h::t->if x <= h then x::l else h::aux x t in aux h (insert_sort t);;
merge_sort
let rec merge_sort l=match l with
[]->[]
|h::t-> let rec repartir=function
[]->([],[])
|h::[]->([h],[])
|h1::h2::t->let (t1,t2)=repartir t in (h1::t1,h2::t2)
in let rec fusion=function
([],l)->l
|(l,[])->l
|(h1::t1,h2::t2)->if h1<h2 then h1::fusion(t1,h2::t2)
else h2::fusion(h1::t1,t2)
in let (l1,l2)=repartir l in fusion(merge_sort l1,merge_sort l2);;
quicksort let rec quicksort=function
[]->[]
|h::t->let rec split x=function
[]->([],[])
|h::t->let(t1,t2)=split h t in if h<=x then (h::t1,t2)
else (t1,h::t2) in let(t1,t2)=split h t
in (quicksort t1)@(h::quicksort t2);;
from0to exception From0to of string;;
let from0to n=match n with
0->[0]
|n->if n<0 then raise(From0to "No se pueden poner numeros negativos")
else let rec aux n=match n with
0->[0]
|n->n::aux (n-1)
in List.rev(aux n);;
to0from exception To0from of string;;
let rec to0from n=match n with
0->[0]
|n->if n<0 then raise(To0from "No se pueden poner numeros negativos")
else n::to0from (n-1);;
fromto m n exception Fromto of string;;
let rec fromto m n=match n with
0->let rec aux n=match n with
0->[0]
|n->if n<0 then raise(Fromto "No se pueden poner numeros negativos") else n::aux (n-1) in aux m
|n->if (m<n) then raise(Fromto "El primer numero debe ser mayor que el segundo")
else (if m=n then [m]
else match m with
0->let rec aux2 n=match n with
0->[0]
|n->if n<0 then raise(Fromto "No se pueden poner numeros negativos")
else let rec aux n=match n with
0->[0]
|n->if n<0 then raise(Fromto "No se pueden poner numeros negativos") else n::aux (n-1) in List.rev(aux n) in aux2 n
|m->if (m<0 or n<0) then raise(Fromto "No se pueden poner numeros negativos")
else m::(fromto (m-1) n));;
randomlist exception Randomlist of string;;
let rec randomlist m n=match n with
0->[]
|n->if (n<0) then raise(Randomlist "No se pueden poner numeros negativos")
else (if (m<=0) then raise(Randomlist "El primer numero debe ser mayor que 0") else (Random.int m)::(randomlist m (n-1)));;
HACER UNA TABLA CON LOS TIEMPOS APROXIMADOS UTILIZADOS POR LAS FUNCIONES insert_sort, merge_sort Y quicksort PARA ORDENAR LISTAS DE 4 LONGITUDES SIGNIFICATIVAS
FUNCION LISTA TIEMPO APROXIMADO
insert_sort from0to 2000 0
from0to 4000 0.0499999999997
from0to 8000 0.0599999999999
from0to 16000 0.0600000000004
to0from 2000 2.2
to0from 4000 10.65
to0from 8000 57.34
to0from 16000 312.74
randomlist 100 2000 0.99
randomlist 100 4000 4.78
randomlist 100 8000 25.15
randomlist 100 16000 136.54
merge_sort from0to 2000
from0to 4000
from0to 8000
from0to 16000
to0from 2000
to0from 4000
to0from 8000
to0from 16000
randomlist 100 2000
randomlist 100 4000
randomlist 100 8000
randomlist 100 16000
quicksort from0to 2000 5.28
from0to 4000 25.54
from0to 8000
from0to 16000
to0from 2000
to0from 4000
to0from 8000
to0from 16000
randomlist 100 2000
randomlist 100 4000
randomlist 100 8000
randomlist 100 16000