03 martie 2010

Sortare prin insertie in Scheme

In Scheme, o sortare se realizeaza in doua etape:
- se creeaza o functie simpla insert care adauga un element intr-o lista deja sortata. Merge pe principiul: ia o lista, verifica primul element, daca e mai mare decat elementul de inserat acesta se va insera chiar inaintea lui, altfel listei i se aplica `tail`, iar listei ce rezulta fara primul element i se aplica acelasi tratament pana cand elementul de inserat isi gaseste locul in lista (recursivitate).
- se creeaza o lista vida in care se vor insera pe rand fiecare element din lista noastra.


(define insert ; insereaza un element intr-o lista deja sortata
(lambda (element lista)
(cond ((null? lista) (list element)) ; daca e lista nula creeaza o noua lista din element
((<= element (car lista)) (cons element lista)) ; daca elementul<=primul element din lista, il pune primul
(else (cons (car lista) (insert element (cdr lista))))))) ; altfel lipeste primul element de restul listei unde element se presupune a fi inserat

(define ls '(20 51 19 13 10))
(define ls_empty '())

(define insertion-sort
(lambda (ls new)
(if (null? ls) new
(let ((new (insert (car ls) new))) (insertion-sort (cdr ls) new))
)
))

(insertion-sort ls ls_empty)

Niciun comentariu: