author | nipkow |
Fri, 04 May 2018 15:59:21 +0200 | |
changeset 68078 | 48e188cb1591 |
parent 67983 | 487685540a51 |
child 68079 | 9c2088adff8b |
permissions | -rw-r--r-- |
66543 | 1 |
(* Author: Tobias Nipkow *) |
2 |
||
3 |
(* FIXME adjust List.sorted to work like below; [code] is different! *) |
|
4 |
||
5 |
theory Sorting |
|
6 |
imports |
|
7 |
Complex_Main |
|
8 |
"HOL-Library.Multiset" |
|
9 |
begin |
|
10 |
||
11 |
hide_const List.sorted List.insort |
|
12 |
||
13 |
declare Let_def [simp] |
|
14 |
||
15 |
fun sorted :: "'a::linorder list \<Rightarrow> bool" where |
|
16 |
"sorted [] = True" | |
|
17 |
"sorted (x # xs) = ((\<forall>y\<in>set xs. x \<le> y) & sorted xs)" |
|
18 |
||
19 |
lemma sorted_append: |
|
20 |
"sorted (xs@ys) = (sorted xs & sorted ys & (\<forall>x \<in> set xs. \<forall>y \<in> set ys. x\<le>y))" |
|
21 |
by (induct xs) (auto) |
|
22 |
||
67983 | 23 |
lemma sorted01: "length xs \<le> 1 \<Longrightarrow> sorted xs" |
24 |
by(auto simp: le_Suc_eq length_Suc_conv) |
|
25 |
||
66543 | 26 |
|
27 |
subsection "Insertion Sort" |
|
28 |
||
29 |
fun insort :: "'a::linorder \<Rightarrow> 'a list \<Rightarrow> 'a list" where |
|
30 |
"insort x [] = [x]" | |
|
31 |
"insort x (y#ys) = |
|
32 |
(if x \<le> y then x#y#ys else y#(insort x ys))" |
|
33 |
||
34 |
fun isort :: "'a::linorder list \<Rightarrow> 'a list" where |
|
35 |
"isort [] = []" | |
|
36 |
"isort (x#xs) = insort x (isort xs)" |
|
37 |
||
68078 | 38 |
|
66543 | 39 |
subsubsection "Functional Correctness" |
40 |
||
41 |
lemma mset_insort: "mset (insort x xs) = add_mset x (mset xs)" |
|
42 |
apply(induction xs) |
|
43 |
apply auto |
|
44 |
done |
|
45 |
||
46 |
lemma mset_isort: "mset (isort xs) = mset xs" |
|
47 |
apply(induction xs) |
|
48 |
apply simp |
|
49 |
apply (simp add: mset_insort) |
|
50 |
done |
|
51 |
||
52 |
lemma set_insort: "set (insort x xs) = insert x (set xs)" |
|
53 |
by (metis mset_insort set_mset_add_mset_insert set_mset_mset) |
|
54 |
||
55 |
lemma set_isort: "set (isort xs) = set xs" |
|
56 |
by (metis mset_isort set_mset_mset) |
|
57 |
||
58 |
lemma sorted_insort: "sorted (insort a xs) = sorted xs" |
|
59 |
apply(induction xs) |
|
60 |
apply(auto simp add: set_insort) |
|
61 |
done |
|
62 |
||
63 |
lemma "sorted (isort xs)" |
|
64 |
apply(induction xs) |
|
65 |
apply(auto simp: sorted_insort) |
|
66 |
done |
|
67 |
||
68078 | 68 |
|
69 |
subsubsection "Time Complexity" |
|
66543 | 70 |
|
71 |
text \<open>We count the number of function calls.\<close> |
|
72 |
||
73 |
text\<open> |
|
74 |
\<open>insort x [] = [x]\<close> |
|
75 |
\<open>insort x (y#ys) = |
|
76 |
(if x \<le> y then x#y#ys else y#(insort x ys))\<close> |
|
77 |
\<close> |
|
78 |
fun t_insort :: "'a::linorder \<Rightarrow> 'a list \<Rightarrow> nat" where |
|
79 |
"t_insort x [] = 1" | |
|
80 |
"t_insort x (y#ys) = |
|
81 |
(if x \<le> y then 0 else t_insort x ys) + 1" |
|
82 |
||
83 |
text\<open> |
|
84 |
\<open>isort [] = []\<close> |
|
85 |
\<open>isort (x#xs) = insort x (isort xs)\<close> |
|
86 |
\<close> |
|
87 |
fun t_isort :: "'a::linorder list \<Rightarrow> nat" where |
|
88 |
"t_isort [] = 1" | |
|
89 |
"t_isort (x#xs) = t_isort xs + t_insort x (isort xs) + 1" |
|
90 |
||
91 |
||
92 |
lemma t_insort_length: "t_insort x xs \<le> length xs + 1" |
|
93 |
apply(induction xs) |
|
94 |
apply auto |
|
95 |
done |
|
96 |
||
97 |
lemma length_insort: "length (insort x xs) = length xs + 1" |
|
98 |
apply(induction xs) |
|
99 |
apply auto |
|
100 |
done |
|
101 |
||
102 |
lemma length_isort: "length (isort xs) = length xs" |
|
103 |
apply(induction xs) |
|
104 |
apply (auto simp: length_insort) |
|
105 |
done |
|
106 |
||
107 |
lemma t_isort_length: "t_isort xs \<le> (length xs + 1) ^ 2" |
|
108 |
proof(induction xs) |
|
109 |
case Nil show ?case by simp |
|
110 |
next |
|
111 |
case (Cons x xs) |
|
112 |
have "t_isort (x#xs) = t_isort xs + t_insort x (isort xs) + 1" by simp |
|
113 |
also have "\<dots> \<le> (length xs + 1) ^ 2 + t_insort x (isort xs) + 1" |
|
114 |
using Cons.IH by simp |
|
115 |
also have "\<dots> \<le> (length xs + 1) ^ 2 + length xs + 1 + 1" |
|
116 |
using t_insort_length[of x "isort xs"] by (simp add: length_isort) |
|
117 |
also have "\<dots> \<le> (length(x#xs) + 1) ^ 2" |
|
118 |
by (simp add: power2_eq_square) |
|
119 |
finally show ?case . |
|
120 |
qed |
|
121 |
||
122 |
||
123 |
subsection "Merge Sort" |
|
124 |
||
125 |
fun merge :: "'a::linorder list \<Rightarrow> 'a list \<Rightarrow> 'a list" where |
|
126 |
"merge [] ys = ys" | |
|
127 |
"merge xs [] = xs" | |
|
128 |
"merge (x#xs) (y#ys) = (if x \<le> y then x # merge xs (y#ys) else y # merge (x#xs) ys)" |
|
129 |
||
130 |
fun msort :: "'a::linorder list \<Rightarrow> 'a list" where |
|
131 |
"msort xs = (let n = length xs in |
|
132 |
if n \<le> 1 then xs |
|
133 |
else merge (msort (take (n div 2) xs)) (msort (drop (n div 2) xs)))" |
|
134 |
||
135 |
declare msort.simps [simp del] |
|
136 |
||
68078 | 137 |
|
67983 | 138 |
subsubsection "Functional Correctness" |
139 |
||
140 |
lemma mset_merge: "mset(merge xs ys) = mset xs + mset ys" |
|
141 |
by(induction xs ys rule: merge.induct) auto |
|
142 |
||
143 |
lemma "mset (msort xs) = mset xs" |
|
144 |
proof(induction xs rule: msort.induct) |
|
145 |
case (1 xs) |
|
146 |
let ?n = "length xs" |
|
147 |
let ?xs1 = "take (?n div 2) xs" |
|
148 |
let ?xs2 = "drop (?n div 2) xs" |
|
149 |
show ?case |
|
150 |
proof cases |
|
151 |
assume "?n \<le> 1" |
|
152 |
thus ?thesis by(simp add: msort.simps[of xs]) |
|
153 |
next |
|
154 |
assume "\<not> ?n \<le> 1" |
|
155 |
hence "mset (msort xs) = mset (msort ?xs1) + mset (msort ?xs2)" |
|
156 |
by(simp add: msort.simps[of xs] mset_merge) |
|
157 |
also have "\<dots> = mset ?xs1 + mset ?xs2" |
|
158 |
using \<open>\<not> ?n \<le> 1\<close> by(simp add: "1.IH") |
|
159 |
also have "\<dots> = mset (?xs1 @ ?xs2)" by (simp del: append_take_drop_id) |
|
160 |
also have "\<dots> = mset xs" by simp |
|
161 |
finally show ?thesis . |
|
162 |
qed |
|
163 |
qed |
|
164 |
||
165 |
lemma set_merge: "set(merge xs ys) = set xs \<union> set ys" |
|
166 |
by(induction xs ys rule: merge.induct) (auto) |
|
167 |
||
168 |
lemma sorted_merge: "sorted (merge xs ys) \<longleftrightarrow> (sorted xs \<and> sorted ys)" |
|
169 |
by(induction xs ys rule: merge.induct) (auto simp: set_merge) |
|
170 |
||
171 |
lemma "sorted (msort xs)" |
|
172 |
proof(induction xs rule: msort.induct) |
|
173 |
case (1 xs) |
|
174 |
let ?n = "length xs" |
|
175 |
show ?case |
|
176 |
proof cases |
|
177 |
assume "?n \<le> 1" |
|
178 |
thus ?thesis by(simp add: msort.simps[of xs] sorted01) |
|
179 |
next |
|
180 |
assume "\<not> ?n \<le> 1" |
|
181 |
thus ?thesis using "1.IH" |
|
182 |
by(simp add: sorted_merge msort.simps[of xs] mset_merge) |
|
183 |
qed |
|
184 |
qed |
|
185 |
||
68078 | 186 |
|
187 |
subsubsection "Time Complexity" |
|
67983 | 188 |
|
189 |
text \<open>We only count the number of comparisons between list elements.\<close> |
|
66543 | 190 |
|
191 |
fun c_merge :: "'a::linorder list \<Rightarrow> 'a list \<Rightarrow> nat" where |
|
192 |
"c_merge [] ys = 0" | |
|
193 |
"c_merge xs [] = 0" | |
|
194 |
"c_merge (x#xs) (y#ys) = 1 + (if x \<le> y then c_merge xs (y#ys) else c_merge (x#xs) ys)" |
|
195 |
||
196 |
lemma c_merge_ub: "c_merge xs ys \<le> length xs + length ys" |
|
197 |
by (induction xs ys rule: c_merge.induct) auto |
|
198 |
||
199 |
fun c_msort :: "'a::linorder list \<Rightarrow> nat" where |
|
200 |
"c_msort xs = |
|
201 |
(let n = length xs; |
|
202 |
ys = take (n div 2) xs; |
|
203 |
zs = drop (n div 2) xs |
|
204 |
in if n \<le> 1 then 0 |
|
205 |
else c_msort ys + c_msort zs + c_merge (msort ys) (msort zs))" |
|
206 |
||
207 |
declare c_msort.simps [simp del] |
|
208 |
||
209 |
lemma length_merge: "length(merge xs ys) = length xs + length ys" |
|
210 |
apply (induction xs ys rule: merge.induct) |
|
211 |
apply auto |
|
212 |
done |
|
213 |
||
214 |
lemma length_msort: "length(msort xs) = length xs" |
|
215 |
proof (induction xs rule: msort.induct) |
|
216 |
case (1 xs) |
|
217 |
thus ?case by (auto simp: msort.simps[of xs] length_merge) |
|
218 |
qed |
|
219 |
text \<open>Why structured proof? |
|
220 |
To have the name "xs" to specialize msort.simps with xs |
|
221 |
to ensure that msort.simps cannot be used recursively. |
|
222 |
Also works without this precaution, but that is just luck.\<close> |
|
223 |
||
224 |
lemma c_msort_le: "length xs = 2^k \<Longrightarrow> c_msort xs \<le> k * 2^k" |
|
225 |
proof(induction k arbitrary: xs) |
|
226 |
case 0 thus ?case by (simp add: c_msort.simps) |
|
227 |
next |
|
228 |
case (Suc k) |
|
229 |
let ?n = "length xs" |
|
230 |
let ?ys = "take (?n div 2) xs" |
|
231 |
let ?zs = "drop (?n div 2) xs" |
|
232 |
show ?case |
|
233 |
proof (cases "?n \<le> 1") |
|
234 |
case True |
|
235 |
thus ?thesis by(simp add: c_msort.simps) |
|
236 |
next |
|
237 |
case False |
|
238 |
have "c_msort(xs) = |
|
239 |
c_msort ?ys + c_msort ?zs + c_merge (msort ?ys) (msort ?zs)" |
|
240 |
by (simp add: c_msort.simps msort.simps) |
|
241 |
also have "\<dots> \<le> c_msort ?ys + c_msort ?zs + length ?ys + length ?zs" |
|
242 |
using c_merge_ub[of "msort ?ys" "msort ?zs"] length_msort[of ?ys] length_msort[of ?zs] |
|
243 |
by arith |
|
244 |
also have "\<dots> \<le> k * 2^k + c_msort ?zs + length ?ys + length ?zs" |
|
245 |
using Suc.IH[of ?ys] Suc.prems by simp |
|
246 |
also have "\<dots> \<le> k * 2^k + k * 2^k + length ?ys + length ?zs" |
|
247 |
using Suc.IH[of ?zs] Suc.prems by simp |
|
248 |
also have "\<dots> = 2 * k * 2^k + 2 * 2 ^ k" |
|
249 |
using Suc.prems by simp |
|
250 |
finally show ?thesis by simp |
|
251 |
qed |
|
252 |
qed |
|
253 |
||
254 |
(* Beware of conversions: *) |
|
255 |
lemma "length xs = 2^k \<Longrightarrow> c_msort xs \<le> length xs * log 2 (length xs)" |
|
256 |
using c_msort_le[of xs k] apply (simp add: log_nat_power algebra_simps) |
|
66912
a99a7cbf0fb5
generalized lemmas cancelling real_of_int/real in (in)equalities with power; completed set of related simp rules; lemmas about floorlog/bitlen
immler
parents:
66543
diff
changeset
|
257 |
by (metis (mono_tags) numeral_power_eq_of_nat_cancel_iff of_nat_le_iff of_nat_mult) |
66543 | 258 |
|
67983 | 259 |
|
260 |
subsection "Bottom-Up Merge Sort" |
|
261 |
||
262 |
(* Exercise: make tail recursive *) |
|
263 |
fun merge_adj :: "('a::linorder) list list \<Rightarrow> 'a list list" where |
|
264 |
"merge_adj [] = []" | |
|
265 |
"merge_adj [xs] = [xs]" | |
|
266 |
"merge_adj (xs # ys # zss) = merge xs ys # merge_adj zss" |
|
267 |
||
268 |
text \<open>For the termination proof of \<open>merge_all\<close> below.\<close> |
|
269 |
lemma length_merge_adjacent[simp]: "length (merge_adj xs) = (length xs + 1) div 2" |
|
270 |
by (induction xs rule: merge_adj.induct) auto |
|
271 |
||
272 |
fun merge_all :: "('a::linorder) list list \<Rightarrow> 'a list" where |
|
273 |
"merge_all [] = undefined" | |
|
274 |
"merge_all [xs] = xs" | |
|
275 |
"merge_all xss = merge_all (merge_adj xss)" |
|
276 |
||
277 |
definition msort_bu :: "('a::linorder) list \<Rightarrow> 'a list" where |
|
278 |
"msort_bu xs = (if xs = [] then [] else merge_all (map (\<lambda>x. [x]) xs))" |
|
279 |
||
68078 | 280 |
|
67983 | 281 |
subsubsection "Functional Correctness" |
282 |
||
283 |
lemma mset_merge_adj: |
|
284 |
"\<Union># image_mset mset (mset (merge_adj xss)) = \<Union># image_mset mset (mset xss)" |
|
285 |
by(induction xss rule: merge_adj.induct) (auto simp: mset_merge) |
|
286 |
||
287 |
lemma msec_merge_all: |
|
288 |
"xss \<noteq> [] \<Longrightarrow> mset (merge_all xss) = (\<Union># (mset (map mset xss)))" |
|
289 |
by(induction xss rule: merge_all.induct) (auto simp: mset_merge mset_merge_adj) |
|
290 |
||
291 |
lemma sorted_merge_adj: |
|
292 |
"\<forall>xs \<in> set xss. sorted xs \<Longrightarrow> \<forall>xs \<in> set (merge_adj xss). sorted xs" |
|
293 |
by(induction xss rule: merge_adj.induct) (auto simp: sorted_merge) |
|
294 |
||
295 |
lemma sorted_merge_all: |
|
296 |
"\<forall>xs \<in> set xss. sorted xs \<Longrightarrow> xss \<noteq> [] \<Longrightarrow> sorted (merge_all xss)" |
|
297 |
apply(induction xss rule: merge_all.induct) |
|
298 |
using [[simp_depth_limit=3]] by (auto simp add: sorted_merge_adj) |
|
299 |
||
300 |
lemma sorted_msort_bu: "sorted (msort_bu xs)" |
|
301 |
by(simp add: msort_bu_def sorted_merge_all) |
|
302 |
||
303 |
lemma mset_msort: "mset (msort_bu xs) = mset xs" |
|
304 |
by(simp add: msort_bu_def msec_merge_all comp_def) |
|
305 |
||
68078 | 306 |
|
307 |
subsubsection "Time Complexity" |
|
67983 | 308 |
|
309 |
fun c_merge_adj :: "('a::linorder) list list \<Rightarrow> real" where |
|
310 |
"c_merge_adj [] = 0" | |
|
311 |
"c_merge_adj [x] = 0" | |
|
312 |
"c_merge_adj (x # y # zs) = c_merge x y + c_merge_adj zs" |
|
313 |
||
314 |
fun c_merge_all :: "('a::linorder) list list \<Rightarrow> real" where |
|
315 |
"c_merge_all [] = 0" | |
|
316 |
"c_merge_all [x] = 0" | |
|
317 |
"c_merge_all xs = c_merge_adj xs + c_merge_all (merge_adj xs)" |
|
318 |
||
319 |
definition c_msort_bu :: "('a::linorder) list \<Rightarrow> real" where |
|
320 |
"c_msort_bu xs = (if xs = [] then 0 else c_merge_all (map (\<lambda>x. [x]) xs))" |
|
321 |
||
322 |
lemma length_merge_adj: |
|
323 |
"\<lbrakk> even(length xs); \<forall>x \<in> set xs. length x = m \<rbrakk> \<Longrightarrow> \<forall>x \<in> set (merge_adj xs). length x = 2*m" |
|
324 |
by(induction xs rule: merge_adj.induct) (auto simp: length_merge) |
|
325 |
||
326 |
lemma c_merge_adj: "\<forall>x \<in> set xs. length x = m \<Longrightarrow> c_merge_adj xs \<le> m * length xs" |
|
327 |
proof(induction xs rule: c_merge_adj.induct) |
|
328 |
case 1 thus ?case by simp |
|
329 |
next |
|
330 |
case 2 thus ?case by simp |
|
331 |
next |
|
332 |
case (3 x y) thus ?case using c_merge_ub[of x y] by (simp add: algebra_simps) |
|
333 |
qed |
|
334 |
||
335 |
lemma c_merge_all: "\<lbrakk> \<forall>x \<in> set xs. length x = m; length xs = 2^k \<rbrakk> |
|
336 |
\<Longrightarrow> c_merge_all xs \<le> m * k * 2^k" |
|
337 |
proof (induction xs arbitrary: k m rule: c_merge_all.induct) |
|
338 |
case 1 thus ?case by simp |
|
339 |
next |
|
340 |
case (2 x) |
|
341 |
then show ?case by (simp) |
|
342 |
next |
|
343 |
case (3 x y xs) |
|
344 |
let ?xs = "x # y # xs" |
|
345 |
let ?xs2 = "merge_adj ?xs" |
|
346 |
obtain k' where k': "k = Suc k'" using "3.prems"(2) |
|
347 |
by (metis length_Cons nat.inject nat_power_eq_Suc_0_iff nat.exhaust) |
|
348 |
have "even (length xs)" using "3.prems"(2) even_Suc_Suc_iff by fastforce |
|
349 |
from "3.prems"(1) length_merge_adj[OF this] |
|
350 |
have 2: "\<forall>x \<in> set(merge_adj ?xs). length x = 2*m" by(auto simp: length_merge) |
|
351 |
have 3: "length ?xs2 = 2 ^ k'" using "3.prems"(2) k' by auto |
|
352 |
have 4: "length ?xs div 2 = 2 ^ k'" |
|
353 |
using "3.prems"(2) k' by(simp add: power_eq_if[of 2 k] split: if_splits) |
|
354 |
have "c_merge_all ?xs = c_merge_adj ?xs + c_merge_all ?xs2" by simp |
|
355 |
also have "\<dots> \<le> m * 2^k + c_merge_all ?xs2" |
|
356 |
using "3.prems"(2) c_merge_adj[OF "3.prems"(1)] by (auto simp: algebra_simps) |
|
357 |
also have "\<dots> \<le> m * 2^k + (2*m) * k' * 2^k'" |
|
358 |
using "3.IH"[OF 2 3] by simp |
|
359 |
also have "\<dots> = m * k * 2^k" |
|
360 |
using k' by (simp add: algebra_simps) |
|
361 |
finally show ?case . |
|
362 |
qed |
|
363 |
||
364 |
corollary c_msort_bu: "length xs = 2 ^ k \<Longrightarrow> c_msort_bu xs \<le> k * 2 ^ k" |
|
365 |
using c_merge_all[of "map (\<lambda>x. [x]) xs" 1] by (simp add: c_msort_bu_def) |
|
366 |
||
66543 | 367 |
end |