LISTE - Sortare prin interschimbare

Liste - Sortare prin interschimbare

Aceasta clasa de algoritmi are un element comun: - interschimbarea sistematica a perechilor de elemente care nu sunt in ordine pana cand nu mai exista astfel de perechi.

Dintre algoritmii apartinind acestei familii vom discuta doar doi: - sortarea cu interschimbare si selectie (numita si metoda bulelor) si sortarea cu interschimbarea partilor (sortare rapida propusa de C.A.R. Hoare).

Vom lucra in continuare cu alocarea inlantuita a inregistrarilor (alocarea dinamica), iar pentru aceasta este preferabil legarea lor intr-o lista dublu inlantuita. Se presupune ca inregistrarile sunt prezentate toate odata (spre deosebire de sortarea prin insertie, unde inregistrarile sosesc una dupa alta, de pe mediul de intrare). Pentru aceasta, o prima etapa in procesul de sortare o constitiue formarea listei cu elementele ce urmeaza a fi sortate, citite de pe un mediu de intrare.

Structura unui element din lista va fi urmatoarea:

typedef struct listai

*plistai;

unde 'k', 'i' reprezinta cimpurile alocate cheii de identificare si informatiei utile, iar 'left', 'right' reprezinta pointerii de legatura a elementului din lista (spre stinga, respectiv spre dreapta).

1. Sortarea prin metoda bulelor

Aceasta metoda este probabil cea mai evidenta cale de sortare prin interschimbari si consta in compararea cheilor k1 si k2 si interschimbarea inregistrarilor R1 si R2 daca cheile nu sunt in ordine, apoi se va face acelasi lucru cu inregistrarile R2 si R3, etc..

In timpul acestei secvente de operatii, inregistrarile cu chei mici tind sa se deplaseze spre stinga si iregistrarea cu cheia cea mai mare va avansa pentru a deveni Rn. Repetarea acestui proces va pune pe locurile lor inregistrarile R(n-1), R(n-2), etc., astfel incit toate inregistrarile vor fi sortate.

Pentru a descrie cat mai simplu acest algoritm vom nota inregistrarile ca pentru o alocare secventiala, desi in implementarea lui vom folosi pointeri de parcurgere a listei.

Presupunind ca sunt 'n' inregistrari de sortat, algoritmul de sortare se poate descrie astfel:

pentru i=n la 2, decrementand cu -1 executa

| pentru j=1 la i executa

| | daca k(j-1)>kj atunci

| | | k(j-1)<--kj

| | |__x

| |__x

|__x

Pentru implementare, pointerul p1 va parcurge lista de la elementul al 2-lea la ultimul element, pointerul p2 va parcurge lista de la ultimul element la elementul curent indicat de pointerul p1.

Pentru interschimbarea elementelor indicate de p1 si cel anterior lui trebuie executate urmatoarele actiuni:

(1) p21=p2->left;

p2->left=p21->left;

p21->left->right=p2;

p21->right=p2->right;

(2) p2->right->left=p21;

p21->left=p2;

p2->right=p21;

p2=p21;

Daca elementul indicat de p2 este ultimul din lista (pu=p2), atunci secventa (2) va trebui inlocuita cu: (2') pu:=p21.

Programul ce implementeaza acest algoritm de sortare va folosi doua proceduri: 'creare' pentru crearea listei dublu inlantuite a elementelor ce urmeaza a fi sortate (informatiile cimpurilor, 'k' si 'i' se citesc dintr-un fisier text) si 'inters' pentru interschimbarea elementelor indicate de pointerul 'p2' si anteriorul acestuia (elementul din stinga); pointerii 'pp' si 'pu' stabilesc primul si ultimul element al listei.

#include <stdio.h>

#include <alloc.h>

#include <stdlib.h>

typedef struct listai

plisti;

plisti *p1, *p2, *pu, *pp;

FILE* f;

void creare()

void inters(plisti **p2)

else *p2 = p21;

void main()

pp = NULL;

pu = pp;

creare();

fclose(f);

p1 = pp;

while (p1 != NULL)

printf('Inregistrarile sortate sint:n');

p1 = pp;

while (p1 != NULL)

2.Sortare rapida

Aceasta metoda foloseste o strategie in care rezultatele fiecarei comparatii stabilesc cheile ce urmeaza a fi comparate.

Vom considera urmatoarea schema de comparatie cu interschimbare asemanatoare cu o ardere de lumanare la ambele capete, considerand doi indicatori 'i' si 'j' (initial i=1, j=n). Se compara ki cu kj; - daca nu e necesar interschimbul se micsoreaza 'j' cu 1 si se continua procesul de comparare. Daca apare un interschimb se mareste 'i' cu 1 si se continua compararea, marind 'i' pina la un nou interschimb. Apoi se micsoreaza din nou 'j', continuind in acelasi mod, pina cind i=j.

In acest fel fiecare comparatie va implica valoarea initiala a primei inregistrari (R1), ajungind ca atunci cind i=j, respectiva inregistrare sa fie plasata in pozitie finala, k=i=j (nu vor exista chei mai mari in stinga si nici chei mai mici in dreapta).

Lista initiala va fi pozitionata astfel in doua subliste: R1, , R(k-1) si R(k+1), , Rn, iar pentru ficare din cele doua subliste se poate repeta acelasi procedeu, pina cind toata lista va fi sortata.

Limitele sublistei ce urmeaza a fi prelucrate se pot memora intr-o stiva. De fiecare data cind o lista este divizata, una din cele doua subliste se plaseaza in stiva (prin capetele ei) si se incepe lucrul cu cealalta sublista, pina se obtin liste extrem de scurte, de doua elemente (se pot ordona printr-o singura interschimbare eventual).

Procesul de sortare se termina cind stiva respectiva devine vida.

Pentru descrierea simplificata a scindarii unei liste in doua subliste, cit si a procesului de sortare propriu-zis, folosim aceasi metoda indiciala (ca pentru o alocare secventiala), urmarind ca la implementarea lor sa folosim pointeri de parcurgere a listelor.

Algoritmul urmator pozitioneaza o lista cu capetele Ri si Rj, rezultind elementul Rk ce va fi plasat pe locul sau final, cit si pozitia k a acestuia. Variabila 'r' este folosita pentru a determina intervalul dintre doua interschimburi si va avea alternativ valoarea +1 si -1.

r<---1

l<---i

p<---j

repeta

daca k1>=kp atunci

| k1<--->kp

| r<--- -r

daca r=1 atunci

| p<---p-1

|altfel

| l<---l+1

pina cind l=p

k<---1

Pentru a descrie algoritmul propriu-zis de sortare rapida, se presupun cunoscute procedurile:

- push (i,j) care introduce in stiva valoarea capetelor sublistei ce urmeaza a fi prelucrate;

- pop (i,j) care scoate din stiva capetele sublistei ce urmeaza a fi prelucrate;

- poz (i,j;k) care pozitioneaza lista de capete 'i' si 'j', primul element pe pozitia sa finala, indicata de variabila k.

Presupunem 'n' ca fiind numarul total al inregistrarilor ce urmeaza a fi sortate, putem descrie algoritmul de sortare in modul urmator:

i<---1

j<---1

push (i,j)

repeta

pop (i,j)

cit timp i<j executa

| poz (i,j,k)

| daca k+1<j atunci

| | push (k+1,j)

| j<---k-1

pina cind stiva vida

Pentru memorarea inregistrarilor ce vor fi sortate vom pastra aceasi structura de lista dublu inlantuita. Realizarea interschimbarii inregistrarilor Ri si Rj se face folosind doi pointeri ce indica spre acestea (notati p1 si p2) in modul urmator:

p12=p1->right;

p1->right=p2->right;

p2->right->left=p1;

p1->left=p2->left;

p2->left->right=p1;

(1) p12->left=p2;

p2->right=p12;

p2->left=p11;

p11->right=p2;

Daca elementul indicat de pointerul p1 este primul element al listei (pp=p1) atunci relatia (1) devine: (1') pp:=p2, iar daca elementul, indicat de p2 este ultimul element al listei (pu=p2) atunci relatia (2) devine: (2') pu:=p1; Stiva ce memoreaza capetele sublistelor ce urmeaza a fi prelucrate va avea urmatoarea structura:

typedef struct stiva

pstiv;

Programul ce implementeaza algoritmul de sortare rapida va folosi procedurile 'push', 'pop' si 'poz' specificate anterior (pentru introducerea si scoaterea din stiva a capetelor de sublista, respectiv pentru pozitionarea primului element al unei subliste in curs de prelucrare pe pozitia sa finala si specificarea acestei pozitii) precum si procedura 'creare' descrisa in programul anterior pentru crearea listei dublu inlantuite cu inregistrarile ce urmeaza sa fie sortate si procedura 'inter' pentru interschimbarea a doua inregistrari specificate prin doi pointeri (p1 si p2).

In locul stivei se foloseste o lista de tipul 'plist'.

#include <stdio.h>

#include <stdlib.h>

#include <ctype.h>

typedef struct lista

plist;

plist *p, *pp, *pu;

FILE *f;

void creare(void)

void inter(plist *p1, plist *p2, plist **pa, plist **pb)

else

p2->left = p11;

if (*pa == p1) *pa = p2;

else p11->right = p2;

void poz(plist **pa, plist **pb)

if (r == 1) p2 = p2->left;

else p1 = p1->right; } while (!(p1 == p2));

poz(pa,&p1);

poz(&p1->right,pb);

}

void main()

Probleme propuse

1. Sa se scrie un program de sortare prin metoda bulelor, folosind inlantuirea elementelor intr-o lista circulara.

2. Sa se scrie un program de sortare directa folosind o varianta recursiva. (folosirea stivei).

3. Pentru gestiunea produselor unei societati, pentru fiecare produs trebuie gestionate urmatoarele informatii: numele produsului, codul produsului, pretul produsului, numarul de produse de tipul respectiv.

Se cere:

a) Sa se creeze o lista liniara dublu inlantuita cu produsele societatii existente in stoc intr-o anumita zi.

b) Sa se ordoneze lista curenta ramasa dupa valoarea totala a produselor din fiecare tip, folosind metoda bulelor.

4. Se considera ca la recensamintul populatiei se iau in considerare urmatoarele informatii: nume, prenume, grupa de studii (primar, mediu, universitar), adresa (articol cu variante - strada si numarul sau strada, blocul, scara, etajul, apartamentul), virsta, sexul.

Se cere:

a) Sa se creeze o lista circulara dublu legata cu persoanele recenzate de catre un anumit recenzor;

b) Sa se ordoneze apoi aceasta lista dupa nume si prenume folosind sortare rapida.

5. Se considera doua liste liniare simplu legate cu cimpurile de informatie utila de tip sir de caractere. Se cere sa se construiasca o lista care contine reuniunea celor doua liste si in care elementele sint ordonate crescator, folosind sortarea prin metoda bulelor.

6. Scrieti un program care combina algoritmii de sortare Quicksort su Bubblesort astfel: utilizeaza Quicksort pentru obtinerea de partitii nesortate de lungime m, 1<=m<=n, apoi utilizeaza Bubblesort pentru terminarea sortarii.

7. Scrieti un program care combina algoritmii de sortare Quicksort si insertie directa astfel: utilizeaza Quicksort pentru obtinerea de partitii nesortate de lungime m, 1<=m<=n, apoi utilizeaza insertia directa pentru terminarea sortarii.

8. Se cere sa se realizeze un program care efectueaza calculul mediilor candidatilor la un concurs de admitere ce consta din 3 probe, repartizarera acestora dupa optiuni (se considera ca exista doua optiuni in limita numarului de locuri disponibile) precum si afisarea in ordinea mediilor a candidatilor neadmisi. La medii egale (calculate cu doua zecimale prin trunchiere) departajarea se face dupa nota la prima proba. Se admite depasirea numarului de locuri in caz de egalitate si dupa acest criteriu. (Se foloseste metoda sortarii rapide)

9. Sa se completeze programul din problema anterioara cu rutine care sa efectueze urmatoarele operatii solicitate intr-un concurs de admitere:

a) Ordonarea alfabetica a tuturor candidatilor si repartizarea lor pe sali pentru probele scrise pe baza unui tabel al salilor cu numarul de locuri din fiecare sala, cu tiparirea listelor pe sali;

b) Realizarea corespondentei intre lucrari dupa deschiderea acestora si numele candidatului (se considera ca fiecare candidat are si un cod unic primit la inscriere).

10. Pentru gestiunea programului de invatamint al unei grupe de studenti dintr-o facultate pe durata unui semestru trebuie alcatuita o lista a tuturor disciplinelor predate in semestrul respectiv. Pentru fiecare disciplina in parte intereseaza: numele disciplinei, numele, prenumele si functia (sef lucrari, conferentiar sau profesor) celui care tine cursul, numarul de ore pe saptamina (1, 2, 3, 4), daca este sau nu prevazuta cu examen sau colocviu la sfirsitul semestrului precum si daca este prevazuta cu seminar, proiect sau laborator. In caz afirmativ se vor specifica numele, prenumele si functia celui care tine aceste ore precum si numarul de ore pe saptamina. Pentru specificarea cadrelor didactice se gestioneaza o lista a cadrelor didactice care contine numele si prenumele acestora precum si functia. Cimpurile din lista de discipline corespunzatoare cadrelor didactice sint pointeri catre elementele listei cadrelor didactice.

Se cere:

a) Sa se construiasca cele doua liste de discipline si de cadre didactice astfel incit lista cadrelor didactice sa fie ordonata dupa functia acestora, in caz de functii egale ordonarea facindu-se alfabetic;

b) Pentru fiecare cadru didactic sa se afiseze disciplinele predate, forma de predare (curs, seminar, laborator, proiect) precum si numarul de ore predate pe saptamina;

c) Sa se ordoneze lista de discipline dupa numarul total de ore alocate pe saptamina fiecarei discipline. In caz de numere de ore alocate pe saptamina egale se va tine cont de numarul de ore de curs, seminar, laborator, proiect, in aceasta ordine si daca si in acest caz avem egalitate se va face ordonare alfabetica. Sa se afiseze apoi lista de discipline ordonata.

11. Se va considera aceeasi problema ca si cea anterioara cu singura diferenta ca exista doua liste de cadre didactice: lista cadrelor didactice titulare si lista cadrelor didactice asociate. La punctul a) se vor construi cele 3 si nu cele doua liste, iar lista cadrelor didactice asociate va fi ordonata alfabetic.

12. Se considera o functie logica complet specificata de "n" variabile reprezentata sub forma unei sume de mintermeni. Mintermenii functiei sint pastrati intr-o lista.

Se cere:

a) Construirea listei mintermenilor functiei;

b) Ordonarea listei mintermenilor functiei dupa ponderea fiecarui mintermen (numarul de biti 1 din cadrul indicatorului binar al mintermenului), iar in caz de ponderi egale, dupa valoarea indicatorului zecimal al mintermenului.