Skip to content

Instantly share code, notes, and snippets.

@miyukino
Created May 26, 2013 08:42
Show Gist options
  • Save miyukino/5652107 to your computer and use it in GitHub Desktop.
Save miyukino/5652107 to your computer and use it in GitHub Desktop.
Scheme: Insertion Sort
;; same as the merge function in MergeSort.scm
(define (insert L M)
(if (null? L) M
(if (null? M) L
(if (< (car L) (car M))
(cons (car L) (insert (cdr L) M))
(cons (car M) (insert (cdr M) L))))))
;; another insert function
;; need to modify the first para in insertionsort function to (car L)
(define (insert2 x L)
(if (null? L) (list x)
(let ((y (car L)) (M (cdr L)))
(if (< x y)
(cons x L)
(cons y (insert2 x M))))))
;; Exp. (insertionsort '(4 2 10 3 -1 5)) ==> (-1 2 3 4 5 10)
(define (insertionsort L)
(if (null? L) '()
(insert (list (car L)) (insertionsort (cdr L)))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment