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

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

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

  1. 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))

Leave a Reply

Your email address will not be published.