[Scheme] Scheme – examples – 3 sorting algorithms + depth of tree

[Scheme] Scheme – examples – 3 sorting algorithms + depth of tree

Comments 4 comments

Here are my 3 basic sorting algorithms written in Scheme:

  • insertion sort: 
    (define (part x y)
  (if (eqv? (car x) y)
      (cdr x)
      (cons (car x) (part (cdr x) y))
  )
)
 
(define (sort2 x)
  (if (null? x)
      x
      (cons (apply min x) (sort2 (part x (apply min x))))
  )
)
 
(sort2 '(4 5 -4 5 1 0 3 2))

    > > (-4 0 1 2 3 4 5 5)

  • merge sort: 
    (define (part x a b f)
  (if (null? x)
      (list a b)
      (if f
          (part (cdr x) (cons (car x)  a) b (not f))
          (part (cdr x) a (cons (car x) b)   (not f))
      )
  )
)
 
(define (merge a b x)
  (cond
      ((null? a) (append (reverse b) x))
      ((null? b) (append (reverse a) x))
      (else (if (< (car a) (car b))
                (merge (cdr a) b (cons (car a) x))
                (merge a (cdr b) (cons (car b) x))
            )
      )
  )
)
 
(define (sortm x)
  (if (null? (cdr x))
      x
      (let* (
            	(par (part x '() '() #t))
            	(l (sortm (car par)))
       	  	(r (sortm (cadr par)))
            )
            (reverse (merge l r '()))
      )
  )
)
 
(sortm '(4 2342 56421 1 213 52 1 5451 -5 2 -4 2 -1 -111))

    >>(-111 -5 -4 -1 1 1 2 2 4 52 213 2342 5451 56421)

  • Quicksort 
    (define (part x a b f)
  (if (null? x)
      (list a b)
      (if (< (car x) f)
          (part (cdr x) (cons (car x)  a) b f)
          (part (cdr x) a (cons (car x) b)  f)
      )
  )
)
 
(define (qsort x)
  (if (null? x)
       x
       (if (null? (cdr x))
           x
           (let* (
                  (par (part (cdr x) '() '() (car x)))
                  (l (qsort (car par)))
                  (r (qsort (cadr par)))
                  )
             (append l (list (car x)) r)
           )
       )
   )
)
 
(qsort '(54 4562 243 26345 123 53 -234 -2 -4 -6 1 4 5 -5 5 -5 9 0))

    > > (-234 -6 -5 -5 -4 -2 0 1 4 5 5 9 53 54 123 243 4562 26345)

And here is an example of computing depth of tree:

  • (define
  (depth x)
      (begin
        (if (or (null? x) (not (pair? x) ) )
            0
            (max
                 ( + 1 (depth (car x)) )
                 (depth (cdr x))
            )
        )
      )
)
 
(depth '( ( ( 1 2 ) ( 3 4 ) ( ( 4 5 ) ( 6 ( 7 ) ) ) ) ) )
(depth '( 1 ) )
(depth '( 1 ( 2 ( 3 ( 4 ) ) ) ) )

    > > 5
    > 1
    > 4

I’ve used http://www.plt-scheme.org/software/mzscheme/

4 thoughts on “[Scheme] Scheme – examples – 3 sorting algorithms + depth of tree”

  3. If you use the instruction (begin ….) is not any more a functional programming experience !

    an example the quick-sort in a functional way, can be like this:

    (define (larger-items alon threshold)
    (cond
    [(empty? alon) empty]
    [else (if (> (first alon) threshold)
    (cons (first alon) (larger-items (rest alon) threshold))
    (larger-items (rest alon) threshold))]))

    (define (smaller-items alon threshold)
    (cond
    [(empty? alon) empty]
    [else (if (< (first alon) threshold)
    (cons (first alon) (smaller-items (rest alon) threshold))
    (smaller-items (rest alon) threshold))]))

    (define (q-sort alon)
    (cond
    [(empty? alon) empty]
    [else (append (q-sort (smaller-items alon (first alon)))
    (list (first alon))
    (q-sort (larger-items alon (first alon))))]))

    (equal? (q-sort (list 1 4 2 65 67 72 1 3 52 3)) (list 1 2 3 4 52 65 67 72))

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *