forked from jeapostrophe/exp
-
Notifications
You must be signed in to change notification settings - Fork 0
/
isort-cost.rkt
47 lines (41 loc) · 1.24 KB
/
isort-cost.rkt
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
#lang racket
(require math/base
plot)
(define (insert-cost n inverted?)
(if inverted?
n
1))
(define (isort-cost n is)
(cond
[(zero? n)
0]
[else
(+ (insert-cost (sub1 n) (first is))
(isort-cost (sub1 n) (rest is)))]))
(define (average l)
(if (empty? l)
0
(/ (sum l) (length l))))
(define (list-with-m-trues-and-n-elements n m)
(build-list n (λ (x) (< x m))))
(define (perms-with-m-trues-and-n-elements n m)
(remove-duplicates (permutations (list-with-m-trues-and-n-elements n m))))
(module+ main
(plot-new-window? #t)
(parameterize ([plot-title "Insertion Sort Cost"]
[plot-x-label "n"]
[plot-y-label "i"]
[plot-z-label "cost"])
(plot3d
(contour-intervals3d (λ (n i)
(argmax (λ (x) x)
(map (λ (p)
(isort-cost (floor n) p))
(perms-with-m-trues-and-n-elements (floor n) (floor (min n i))))))
0 8
0 8))
(plot3d
(contour-intervals3d (λ (n i)
(* n n))
0 8
0 8))))