Sortari: Insert-Sort, Bubble-Sort, Quick-Sort
<![CDATA[
/*****************************************
* Sortarea crescatoare unei liste de reali, prin:
* - Metoda insertiei
* - Metoda bubblesort
* - Metoda quicksort
* Paul Mateescu, grupa 309-Informatica, an III-ZI, 2009.
* Facultatea de Matematica si Informatica, Universitatea Spiru Haret Bucuresti.
*******************************************/
domains
r = real
i = integer
lr = r*
llr = lr*
predicates
%: Sortare crescatoare a unui sir, prin metoda insertiei
inss(lr, lr) % interfata cu utilizatorul
inss(lr, lr, lr) % realizeaza sortarea propriu-zisa
insert(lr, r, lr) % insera un real intr-o lista de reali deja sortata crescator, pt a obtine o noua lista sortata
%: Sortare crescatoare a unui sir, prin metoda bubblesort:
bubbles(lr, lr) % interfata cu utilizatorul
bubbles(lr, lr, lr, i, lr) % realizeaza sortarea propriu-zisa
%: Sortare crescatoare a unui sir, prin metoda quicksort:
quicks(lr, lr) % interfata cu utilizatorul
quicks(r, lr, lr, lr, lr, lr, lr) % realizeaza sortarea propriu-zisa
lconcat(lr, lr, lr) % concateneaza doua liste de reali
clauses
lconcat([], L, L).
lconcat([H|T], L, [H|R]) :- lconcat(T, L, R).
/***************************************************************/
% Predicatul care realizeaza sortarea crescatoare a unei liste de reali prin metoda insertiei:
% (i, o)
% Notand inss(L, LS), semnificatia argumentelor este:
% L - lista de reali care trebuie sortata
% LS - lista sortata
% cheama predicatul care efectueaza sortarea propriu-zisa:
inss(L, LS) :-
inss([], L, LS).
/***************************************************************/
% Predicatul care realizeaza sortarea crescatoare propriu-zisa prin metoda insertiei:
% (i, i, o)
% Notand inss(LSP, LR, LF), semnificatia argumentelor este:
% LSP - lista de reali partiala deja sortata
% LR - lista ramasa de sortat
% LF - lista finala sortata
% Am ajuns la finalul algoritmului:
inss(L, [], L) :- !.
% Insereaza elementul din capul listei ramase de sortat in pozitia corespunzatoare din lista deja sortata, apoi reia cu restul listei de sortat:
inss(L, [H|T], R) :-
insert(L, H, L1),
!,
inss(L1, T, R).
/***************************************************************/
% Predicatul care realizeaza inserarea unui real intr-o lista de reali deja sortata crescator:
% (i, i, o)
% Notand insert(LSI, R, LSF), semnificatia argumentelor este:
% LSI - lista de reali deja sortata
% R - realul de inserat
% LSF - lista finala sortata
% Inca nu am ajuns la pozitia corecta in care trebuie inserat:
insert([A|T], B, [A|R]) :-
A <=B,
!,
insert(T, B, R).
% Am ajuns la pozitia corecta:
insert(T, B, [B|T]).
/***************************************************************/
% Predicatul care realizeaza sortarea crescatoare a unei liste de reali prin metoda bubblesort:
% (i, o)
% Notand bubbles(L, LS), semnificatia argumentelor este:
% L - lista de reali care trebuie sortata
% LS - lista sortata
% cheama predicatul care efectueaza sortarea propriu-zisa:
bubbles(L, LS) :-
bubbles(L, CLS, CLS, 0, LS).
/***************************************************************/
% Predicatul care realizeaza sortarea crescatoare propriu-zisa prin metoda bubblesort:
% (i, i, o, o, o)
% Notand bubbles(LISTA, CAPLS, CRTLS, CH, REZ), semnificatia argumentelor este:
% LISTA - lista de reali care trebuie parcursa la pasul curent
% CAPLS - capul listei rezultate prin prelucrare la pasul curent
% CRTLS - elementul curent al listei prelucrate la pasul curent
% CH - indicator: este 0 daca nu s-a efectuat nicio inversare de elemente la pasul curent, 1 altfel
% REZ - lista finala sortata
% lista mai are cel putin 2 elemente, care sunt in ordinea corecta si nu trebuie inversate:
bubbles([A, B|T], CAPLS, [A|REST], CH, R) :-
A <= B,
!,
bubbles([B|T], CAPLS, REST, CH, R).
% lista mai are cel putin 2 elemente care trebuie inversate:
bubbles([A, B|T], CAPLS, [B|REST], _, R) :-
!,
bubbles([A|T], CAPLS, REST, 1, R).
% lista mai are un singur element:
bubbles([A], CAPLS, [A], CH, R) :-
!,
bubbles([], CAPLS, _, CH, R).
% lista nu mai are elemente la parcurgerea curenta dar s-a efectuat o inversare, deci reluam algoritmul:
bubbles([], CAPLS, _, 1, R) :-
!,
bubbles(CAPLS, CAPLSURM, CAPLSURM, 0, R).
% lista nu mai are elemente si nu s-a mai efectuat nicio ionversare la parcurgerea curenta, deci algoritmul se incheie:
bubbles([], CAPLS, [], 0, CAPLS).
/***************************************************************/
% Predicatul care realizeaza sortarea crescatoare a unei liste de reali prin metoda quicksort:
% (i, o)
% Notand quicks(L, LS), semnificatia argumentelor este:
% L - lista de reali care trebuie sortata
% LS - lista sortata
% Lista vida sortata este tot lista vida:
quicks([], []) :- !.
% cheama predicatul care efectueaza sortarea propriu-zisa:
quicks([H|T], LS) :-
quicks(H, T, CLMC, CLMC, CLMR, CLMR, LS).
/***************************************************************/
% Predicatul care realizeaza sortarea crescatoare propriu-zisa prin metoda quicksort:
% (i, i, o, o, o)
% Descrierea algoritmului:
% se alege ca pivot primul element al listei, apoi restul de elemente din lista se imparte in
% 2 subliste, prima cu elemente <= pivotul, a doua cu elemente > pivotul. Cele 2 subliste se
% sorteaza recursiv cu aceeasi metoda, apoi se concateneaza prima lista sortata cu pivotul si
% cu a doua lista sortata.
% De mentionat ca algoritmul calculeaza simultan cele doua lista printr-o singura parcurgere a
% listei originale.
% Notand quicks(PIVOT, LISTA, CAPLMC, CRTLMC, CAPLMR, CRTLMR, LISTAS), semnificatia argumentelor este:
% PIVOT - pivotul
% LISTA - lista de impartit in doua subliste in functie de pivot
% CAPLMC - capul listei cu elemente <= PIVOT
% CRTLMC - elementul curent al listei cu elemente <= PIVOT
% CAPLMR - capul listei cu elemente > PIVOT
% CRTLMR - elementul curent al listei cu elemente > PIVOT
% LISTAS - lista finala sortata
% lista de sortat e nevida si primul ei element este <= pivotul, deci se adauga la prima lista:
quicks(P, [H|T], CLMC, [H|RLMC], CLMR, CRTLMR, LS) :-
H <= P,
!,
quicks(P, T, CLMC, RLMC, CLMR, CRTLMR, LS).
% lista de sortat e nevida si primul ei element este > pivotul, deci se adauga la prima lista:
quicks(P, [H|T], CLMC, CRTLMC, CLMR, [H|RLMR], LS) :-
!,
quicks(P, T, CLMC, CRTLMC, CLMR, RLMR, LS).
% lista de sortat a ajuns la capat, inchidem cele doua subliste cu lista vida, le sortam recursiv si le concatenam cu pivotul la mijloc:
quicks(P, [], CLMC, [], CLMR, [], LS) :-
!,
quicks(CLMC, CLMCS),
!,
quicks(CLMR, CLMRS),
lconcat(CLMCS, [P|CLMRS], LS).
]]>