Liste - Sortare prin inserare

Liste - Sortare prin inserare

Sortarea prin inserare reprezinta o familie importanta de tehnici de sortare bazata pe tehnica jucatorului de bridge: - se considera sortate inregistrarile r1, r2, r3,, rj-1 si inregistrarea ri se insereaza printre inregistrarile anterioare, astfel incit cele "j" inregistrari sa fie de asemenea sortate.

Vom presupune in continuare ca o inregistrare 'r' contine cimpul de informatie utila 'i', cheia de cautare 'k' si referinta de legatura spre urmatoarea inregistrare 'l'. In acest mod   inregistrarile se pot lega intr-o lista in care elementele au structura:

typedef struct lists

*plist;

Deci inregistrarile r1, r2,rj se considera sortate in cazul in care cheile ki sunt ordonate crescator: k1, k2,,kj.

1. Insertie directa

Considerind deci inregistrarile r1, r2,, rj-1 sortate, pentru introducerea inregistrarii rj, se compara kj cu k1, k2,kj-1 pina ce se descopera ca rj trebuie inserat intre inregistrarile ri si ri+1. Initial lista inregistrarilor este vida, iar prima inregistrare se introduce fara nici o comparare. Lista rezultata va inlocui elementele in sens direct, primul element fiind cel cu cheia cea mai mica, elementul cu cheia cea mai mare (ultimul element) va contine NIL in cimpul de legatura 'l':

Un algoritm pentru sortare prin insertie directa este prezentat mai jos:

- Se considera ca inregistrarea 'r' cu cheia 'k' trebuie inserata:

1) Se insereaza primul element; p0 va indica spre acesta

2) Cit timp mai sunt inregistrari de introdus, se executa urmatorii pasi:

a) Se parcurge lista incepind cu primul element pina cind k <= ki sau li=NIL

b) Daca li=NIL si k > ki, se insereaza "r" dupa ultimul element, altfel se insereaza 'r' inaintea elementului curent.

Pentru a putea scrie un program de sortare prin insertie directa este nevoie de o procedura de inserare a unui element in lista, dupa un element specificat. De aceea lista se parcurge folosind doua variabile referinta p1 si p2, cu p1 fiind inaintea lui p2 cu un element, astfel incit atunci cind se determina k <= ki (ki este cheia inregistrarii desemnate de p1), inregistrarea "r" se va insera intre p1 si p2 (deci dupa p2). In cazul in care p1 ajunge la ultimul element si nu s-a gasit relatia k >= ki, inregistrarea "r" se introduce dupa p1 (deci dupa ultimul element, acesta devenind acum noul ultim element al listei).

Programul de sortare dupa metoda descrisa anterior citeste una cite una inregistrarile dintr-un fisier secvential (fara cimpul de legatura 'l'), le sorteaza, iar la afisare le scrie in ordinea sortarii.

#include <stdlib.h>

#include <alloc.h>

#include <conio.h>

#include <stdio.h>

typedef struct lists

plist;

void main()

else

p->l=p1;

p2->l=p;

}

}

fclose(f);

clrscr();

printf('Inregistrarile sortate sint :n');

p=p0;

if (p!=NULL)

do

while (p!=NULL);

}

2. Insertia binara

Pentru a prelucra a j-a inregistrare in timpul sortarii, trebuie comparate cheia sa cu aproximativ (1/2)*j din cheile sortate anterior; de aceea numarul total de comparatii va fi aproximativ (1/2)*(1+2++n) ~1/n+1, adica destul de mare chiar pentru valori modeste ale lui "n".

Pentru micsorarea numarului de cautari, se poate folosi tehnica de cautare binara, in care al j-lea articol va fi inserat dupa efectuarea a log₂ j comparatii bine alese.

De exemplu, pentru a insera inregistrarea R64 se poate compara K64 cu K32 (mijlocul inregistrarilor deja inserate). Daca este mai mic, il vom compara cu K16, iar daca e mai mare il comparam cu K48 (deci jumatatea subsirului din stinga, sau din dreapta), etc.

Daca vom utiliza in continuare o reprezentare liniara pentru legarea inregistrarilor, dupa gasirea locului pe care il ocupa o inregistrare, urmeaza o deplasare a sirului elementelor din dreapta, ceea ce duce ca numarul total de operatii sa se apropie de "n". De aceea preferam sa utilizam reprezentarea sub forma de arbore binar, in care fiecare element va avea doi descendenti: sting si drept.

O inregistrare R va avea deci urmatoarea structura:

typedef struct arb

parb;

in care 'st' si 'dr' sint pointeri spre elementele descendente din stinga respectiv din dreapta, iar nodurile terminale din arbore vor avea 'st' si 'dr' ca valoare pe NULL.

Sortarea se poate realiza acum inserind pe rind elementele intr-un arbore de cautare binar (vezi si capitolul doi) si apoi listarea lor se face traversind arborele in inordine.

Un algoritm tipic de cautare si inserare este prezentat mai jos, unde s-a notat cu 'rad' variabila referinta ce indica radacina arborelui. Initial se presupune variabila 'rad' ca avind valoarea NULL (arbore vid). De asemenea se noteaza cu K cheia inregistrarilor ce trebuie introduse.

Pas1. (initializare)

Se stabileste p<--rad (variabila "p" se va deplasa de-a lungul arborelui).

Pas2. (comparare)

Daca k<p->k se tece la pas3.

Altfel ( daca k>=p->k ) se trece la pas4.

Pas3. (deplasare spre stinga)

Daca p->st<>null se stabileste p<---p->st si se revine la pas2.

In caz contrar se trece la pas5.

Pas4. (deplasare la dreapta)

Daca p->dr<>null se stabileste p<---p->dr si se revine la pas2.

Pas5. (inserare)

Se aloca spatiu pentru o noua inregistrare (new(q));

Se leaga in arbore: q->k<---k, q->st<---null, q->dr<---null;

Daca k<p->k se stabileste p->st<---q, altfel p->dr<---q; p<---q.

Se poate scrie o procedura de cautare si inserare in arbore a unui element, folosind o varianta recursiva.

void CAUTA(int a, int b, parb **p)

else

if (a<(*p)->k) cauta(a,b,&(*p)->st);

else cauta(a,b,&(*p)->dr);

}

Procedura CAUTA contine ca variabile intregi 'a' si 'b' ce reprezinta cheia si informatia utila a noii inregistrari si variabila referinta 'p' folosita pentru parcurgerea arborelui.

Parcurgerea in inordine a arborelui binar este tot un procedeu recursiv - daca el este vid nu se petrece nimic, altfel traversarea are loc in trei etape:

-se traverseaza subarborele sting;

-se viziteaza (tipareste) radacina arborelui;

-se traverseaza subarborele drept;

O procedura recursiva de parcurgere a unui arbore binar se poate scrie astfel:

void inord(parb *p)

}

Cu aceste lucruri stabilite, putem scrie programul de sortare a inregistrarilor prin insertie binara. Pentru fiecare inregistrare (cheia si informatia utila) se citesc dintr-un fisier secvential.

void main()

printf('Elementele sortate sint: n');

inord(rad);

}

Probleme propuse

1. Sa se scrie un program de sortare prin insertie directa, folosind liste liniare dublu legate.

2. Sa se scrie un program de sortare prin insertie binara folosind pentru algoritmul de cautare si insertie o varianta nerecursiva.

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. Sa se mai creeze inca doua liste liniare dublu legate cu produsele intrate in stoc i cu cele vindute in ziua respectiva. Fiecare element din aceste doua liste este caracterizat prin codul produsului si numarul produselor de tipul respectiv;

b) Sa se actualizeze lista curenta, eliminind din ea produsele epuizate;

c) Sa se ordoneze lista curenta prin insertie directa ramasa dupa valoarea totala a produselor din fiecare tip.

4. Pentru gestiunea abonatilor unei centrale telefonice trebuie pastrate urmatoarele informatii referitoare la fiecare abonat: numele, prenumele, adresa (strada , numar), numar de telefon.

Se cere:

a) Sa se creeze o lista circulara dublu inlantuita cu toti abonatii centralei;

b) Sa se construiasca o lista dublu legata liniara cu numele, prenumele si telefonul abonatilor care au domiciliul pe o strada ce se afla intr-o lista liniara simplu inlantuita de strazi specificate;

c) Sa se ordoneze ultima lista dupa numele si prenumele abonatilor prin insertie directa, iar pentru abonatii cu acelasi nume dupa numerele lor de telefon; sa se listeze apoi toti abonatii la care numarul de telefon contine secventa '81'.

5. 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 iar pentru persoanele cu nume identice dupa virsta;

6. Se considera un sistem matematic specificat prin:

-un sir de identificatori care desemneaza axiomele sistemului;

-un sir de identificatori carec desemneaza teoremele sistemului. Pentru fiecare teorema se specifica si multimea axiomelor si teoremelor ce intra in demonstratia sa.

Se cere:

a) Pentru un sistem matematic dat sa se decida daca el este inchis si necontradictoriu (fiecare teorema a sistemului se poate demonstra);

b) Sa se ordoneze sirul de teoreme prin insertie binara astfel incit pentru fiecare teorema toate teoremele ce intra in demonstratia sa apara inaintea teoremei specificate.

7. 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.

8. 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 si cu tiparirea listelor pe sali;

b) Prelucrarea notelor de la cele doua corectari (pentru lucrari considerate a fi identificate printr-un cod numeric) si elaborarea listelor cu numerele de lucrari ce trebuie trimise la a treia corectare pentru ca au diferente de peste un punct, la media notelor pe subiecte;

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

9. Orasele unei anumite regiuni sint caracterizate prin urmatoarele date: numele orasului, numarul de locuitori, aprecierea economica globala (ce poate fi A, B, C, D, E, cea mai buna este A) si suprafata in kilometri patrati.

Se cere:

a) Sa se creeze o lista liniara cu orasele regiunii respective;

b) Sa se ordoneze lista construita in ordine crescatoare, prin insertie binara, considerind ca ordinea importantei datelor referitoare la un oras (exceptind numele orasului) este cea precizata in enunt si sa se afiseze apoi lista ordonata.

10. Se considera un pachet de carti de joc.

Se cere:

a) Utilizind o functie de randomizare (aleatorizare) sa se simuleze amestecul pachetului si apoi sa se realizeze distributia cartilor la 4 jucatori, cite 13 carti la fiecare;

b) Sa se sorteze apoi cartile corespunzatoare fiecarui jucator din cei 4 conform regulilor jocului de bridge (culoarea este prioritara in ordinea trefla<caro<cupa<pica, iar la culori egale conteaza numarul cartii in ordinea 2<3<<10<J<Q<K<A) si sa se afiseze cele 4 miini sortate.

11. Se considera o retea locala de calculatoare formata din servere si statii de lucru. Fiecare server sau statie de lucru este un calculator compatibil IBM-PC, model XT, AT, PS/1 sau PS/2. Pentru fiecare astfel de calculator intereseaza: tipul procesorului (poate fi 8088, 8086, 80286, 80386, 80486), modelul (oricare din cele 4 mentionate), capacitatea memoriei interne (in Mocteti), numarul de unitati de disc floppy, daca are sau nu harddisk si in caz afirmativ capacitatea acestuia si tipul de adaptor video (se considera ca poate fi oricare dintre: MDA, HERCULES, CGA, EGA sau VGA). Se considera ca reteaua are o structura de graf. Fiecare nod din graf reprezinta un calculator, ar fiecare legatura din graf o conexiune intre doua calculatoare. Reprezentarea grafului se face sub forma unei liste de adiacenta ce contine nodurile grafului si pentru fiecare nod lista vecinilor acestui nod. Fiecarui nod din graf i se asociaza un numar. Datele referitoare la calculatoare se pastreaza intr-o tabela, datele aferente calculatorului din nodul 'i' al retelei fiind plasate in elementul 'i' al tabelei.

Se cere:

a) Construirea structurilor de date corespunzatoare descrierii tabelei;

b) Sortarea in ordine descrescatoare a listei de adiacenta dupa criteriile: server sau statie (se considera statie<server), model calculator (XT<AT< PS/1<PS/2), tip procesor (8088 < 8086 < 80286 < 80386<80486), capacitate memorie interna, daca au sau nu harddisk: are>nu are) iar daca au harddisk in ordine descrescatoare a capacitatii acestuia;

c) Sortarea in ordine descrescatoare pentru fiecare nod din lista de adiacenta a listei vecinilor acestuia conform criteriului de la b);

d) Afisarea listei de adiacenta sortate precum si a listelor vecinilor fiecarui nod din retea, sortate.

12. Se considera o grupa de studenti care au avut de sustinut in ultima sesiune n=5 examene. Pentru gestiunea rezultatelor obtinute in sesiune se alcatuieste o lista cu toti tudentii grupei care pastreaza numele si prenumele fiecarui student si rezultatele obtinute de acesta. Facem observatia ca orice rezultat poate fi: o nota de promovare, cuprinsa intre 5 si 10, o nota insuficienta pentru promovare intre 1 si 4 sau poate specifica faptul ca studentul respectiv nu s-a prezentat la examenul respectiv.

Se cere:

a) Sa se construiasca lista cu numele si prenumele studentilor si rezultatele obtinute de acestia in sesiune;

b) Sa se construiasca apoi, pe baza acestei liste, lista studentilor integralisti, lista studentilor cu un examen nepromovat, lista studentilor cu examene nepromovate si lista studentilor cu mai mult de 2 examene nepromovate, toate ordonate alfabetic si apoi sa se afiseze aceste liste;

c) Sa se ordoneze lista studentilor integralisti dupa media la cele n=5 examene si sa se afiseze;

d) Pentru fiecare i=1, 5 sa se construiasa lista studentilor are nu au promovat disciplina "i", ordonata alfabetic si sa se afiseze.