SHARE
TWEET

zz

a guest Nov 15th, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. (define binary-search
  2.   (lambda (n l low high)
  3.     (if(> low high)
  4.        -1
  5.        (let((mid (floor (/(+ low high) 2))))
  6.          (cond ((= (list-ref l mid) n) mid)
  7.                ((> n (list-ref l mid)) (binary-search n l (+ mid 1) high))
  8.                (else (binary-search n l low (- mid 1)))
  9.                )
  10.          )
  11.        )
  12.     )
  13.   )
  14. (define belong?
  15.   (lambda (n l)
  16.     (>= (binary-search n l 0 (- (length l) 1)) 0)
  17.     )
  18.   )
  19. (define position
  20.   (lambda (n l)
  21.     (binary-search n l 0 (- (length l) 1))
  22.     )
  23.   )
  24. (define insert-rec
  25.   (lambda (l n pos)
  26.     (cond((null? l) (list n))
  27.          ((or (= pos 0) (= pos -1)) (cons n l))
  28.          (else (cons (car l) (insert-rec (cdr l) n (- pos 1))))
  29.          )
  30.     )
  31.   )
  32. (define sorted-ins-rec
  33.   (lambda(n l low high)
  34.     (if(null? l)
  35.        (append (list n) l)
  36.        (let((mid (floor(/ (+ high low) 2))))
  37.          (cond ((belong? n l) l)
  38.                ((> n (list-ref l high)) (insert-rec l n (+ high 1)))
  39.               ((< n (list-ref l low)) (insert-rec l n low))
  40.               ((> n (list-ref l mid)) (sorted-ins-rec n l (+ mid 1) high))
  41.               (else (sorted-ins-rec n l low (- mid 1)))
  42.               )
  43.          )
  44.        )
  45.     )
  46.   )
  47. (define sorted-ins
  48.   (lambda (n l)
  49.     (sorted-ins-rec n l 0 (- (length l) 1))
  50.     )
  51.   )
  52. (define sorted-list-rec
  53.   (lambda (l1 l2)
  54.     (if(null? l1)
  55.        l2
  56.        (sorted-list-rec (cdr l1) (sorted-ins (car l1) l2))
  57.      )
  58.    )
  59.  )
  60. (define sorted-list
  61.   (lambda(l)
  62.     (sorted-list-rec l '())
  63.     )
  64.   )
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top