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)

Forme curry si uncurry in Scheme

In Scheme, functiile au forma curry (isi asteapta parametrii pe rand) sau uncurry (primeste toti parametrii odata)

In urmatorul exemplu, se realizeaza concatenarea a doua liste folosind functii recursive in forma curry si uncurry:

appendcurry.ss


(define l1 '(1 2 3))
(define l2 '(5 6 7))

(define appendc
(lambda (l1)
(lambda (l2)
( if (null? l1) l2
(cons (car l1) ((appendc (cdr l1)) l2 ) ) ) )
))

(display ((appendc l1) l2))


appenduncurry.ss

(define l1 '(1 2 3))
(define l2 '(5 6 7))

(define appendu
(lambda (l1 l2)
( if (null? l1) l2
(cons (car l1) (appendu (cdr l1) l2 ) ) ) )
)

(display (appendu l1 l2))


Trecerea de la curry la uncurry sau invers a unei functii se face astfel:

(define f (lambda(x y) (+ x y)))

; curry -> uncurry

(define uc
(lambda (f)
( lambda(x)
(lambda(y)
(f x y)
))))

(((uc f ) 2 )3)

(define g (lambda (x)
(lambda (y)
(+ x y))))

; uncurry -> curry

( define cu
(lambda (f)
(lambda (x y)
((f x) y))))

((cu g) 2 3)

Protocolul ABP folosind comunicatia prin pipe-uri

Pipe-urile permit comunicatia intre doua procese pe sisteme Unix.
ABP (alternating bit protocol) este un transmitator de date simplu care transmite date corupte sau pierdute. Fiecare mesaj de la A la B contine doua parti: data (ce se transmite propriu-zis) si o secventa de 1 bit (0 sau 1) numita tag. In schimb, B transmite lui A un mesaj de confirmare (ACKnowledgement) ACK0 sau ACK1. Cand A trimite un mesaj, il trimite in mod continuu, pana cand primeste mesajul de confirmare de la B care contine acelasi lucru ca si tag. Cand acest lucru se intampla, A transmite urmatorului mesaj.
Cand B primeste un mesaj care nu este corupt si are ca si continut 0, incepe sa trimita ACK0, pana cand primeste un mesaj valid cu numarul 0. Apoi incepe sa trimita ACK1, etc.

Mai jos, sunt prezentate 2 programe in C care simuleaza transmiterea de date intre doua programe. In Linux se deschid 2 console, unde se creeaza 2 pipe-uri cu numele date in program:

mkfifo pipe1
mkfifo pipe2

Apoi se ruleaza programele in acelasi timp si se observa transmiterea de date.

receiver.c

#include "stdio.h"
#include "unistd.h"
#include "sys/types.h"
#include "string.h"
#include "sys/stat.h"
#include "fcntl.h"

//receiver

int main ()

{
char tag;
int fd1, fd2;
fd1 = open ( "pipe1", O_RDONLY );
fd2 = open ("pipe2", O_WRONLY);

char buf [100];
int p;

while(1) {
read ( fd1, buf, 100 );
p=strlen (buf);
printf ( "%s \n", buf );
tag = buf [p-1];
write (fd2, &tag, 1);
}

close (fd1);
close (fd2);
return 0;
}


sender.c

#include "stdio.h"
# include "string.h"
#include "sys/types.h"
#include "unistd.h"
#include "sys/stat.h"
#include "fcntl.h"

// sender

char * phrase = "Stuff this in your pipe and smoke it";

int main ()

{ int fd1, fd2;
char tag;
fd1 = open ( "pipe1", O_WRONLY );
fd2 = open ("pipe2", O_RDONLY);
int i;
for(i=0 ; i < strlen (phrase); i+=3) {
write (fd1, phrase+i, 3);
read (fd2, &tag, 1);
}
close (fd1);
close(fd2);
return 0;
}

Merge Sort

Algoritmul merge sort execută următorii paşi

1. Dacă lista este de lungime 0 sau 1, atunci este deja sortată. Altfel:
2. Împarte lista nesortată în două subliste aproximativ egale.
3. Sortează fiecare sublistă recursiv prin reaplicarea algoritmului merge sort.
4. Se interclaseaza cele două liste şi se obţine lista iniţială sortată.

#include "stdio.h"
#include "stdlib.h"

int *x;

void merge (int s,int d) {

int *y=(int *)malloc((d-s+1)*sizeof(int));
int i,j,k,m;
m=(s+d)/2;

for(i=s, j=m+1, k=0; i < =m && j < =d; k++)
if(x[i] < x[j])
   y[k]=x[i++];
else y[k]=x[j++];

for(; i < =m; k++)
   y[k]=x[i++];
for(; j < =d; k++)
   y[k]=x[j++];
for(k=0, i=s; k<d-s+1; k++)
   x[k+i]=y[k];
}


void ms (int i,int j) {

if(i < j) { ms(i,(i+j)/2);
  ms((i+j)/2+1,j);
  merge(i,j); }
}


int main()
{
int n, i;
scanf("%d",&n);
x=(int *)malloc(n*sizeof(int));

for(i=0; i < n; i++)
  scanf("%d",&x[i]);
printf("\n");

ms(0,n-1);
for(i=0; i < n ; i++)
   printf("%d ",x[i]);

return 0;

}

Sortare rapida (Quick sort)

Quicksort efectuează sortarea bazându-se pe o strategie divide et impera. Astfel, el împarte lista de sortat în două subliste mai uşor de sortat. Paşii algoritmului sunt:

1. Se alege un element al listei, denumit pivot.
   
2. Se reordonează lista astfel încât toate elementele mai mici decât pivotul să fie plasate înaintea pivotului şi toate elementele mai mari să fie după pivot. După această partiţionare, pivotul se află în poziţia sa finală.
3. Se sortează recursiv sublista de elemente mai mici decât pivotul şi sublista de elemente mai mari decât pivotul.

O listă de dimensiune 0 sau 1 este considerată sortată.

#include "stdlib.h"
#include "time.h"
#include "stdio.h"

int *x;

int poz (int s, int d) {

int i=s, j=d, di=0, dj=1, aux;
while(i < j)
{ if(x[i] > x[j])
{ aux=x[i];
x[i]=x[j];
x[j]=aux;
di=1-di;
dj=1-dj; }
i+=di;
j-=dj; }
return i;
}


void quick (int s, int d) {

if(s < d) { int k=poz(s,d);
quick(s,k-1);
quick(k+1,d); }
}

int main () {

srand(time(NULL));
int n;
scanf("%d",&n);
x=(int *)malloc(n*sizeof(int));

int i;
for(i=0; i < n ;i++)
x[i]=rand()%100;
for(i=0; i < n ;i++)
printf("%d ",x[i]);
quick(0,n-1);

printf("\n");
for(i=0; i < n ;i++)
printf("%d ",x[i]);
printf("\n");

return 0;
}