LISTE - Sortare prin interclasare

Liste - Sortare prin interclasare

Interclasarea 'inseamna' combinarea a doua sau mai multe grupuri de inregistrari ordonate.

Pentru interclasarea interna se considera doua sau mai multe liste de inregistrari ordonate si se genereaza o singura lista continind toate inregistrarile listelor de intrare, de asemenea ordonate.

In continuare vom considera doar cazul a doua liste.

Fie deci listele L1 si L2 ce contin inregistrarile: R1, R2, R3,, Rn, respectiv R'1, R'2, .., R'm astfel incit cheile lor sa fie ordonate: K1 <= K2 <= <=Kn si respectiv K'1 <= K'2 <= K'm. Va trebui creata o lista L cu m+n inregistrari (R'1, R'2,,R'm+n) astfel incit sa avem: K'1 <= K'2 <= <=K'm+n

Presupunem listele L1, L2 si L ca fiind simplu inlantuite, iar elementele lor au structura urmatoare:

typedef struct lista

plist;

Cel mai simplu algoritm de interclasare presupune extragerea pe rind a cite unui element din lista L2 (cel mai mic deci) si inserarea lui in lista L1. Acest procedeu se continua pina cind lista devine vida (lista L2), moment in care lista L1 reprezinta chiar lista L dorita.

Inserarea elementelor in lista L1 se presupune ca se face prin procedeul insertiei directe.

Programul pentru interclasarea a doua liste ordonate presupune crearea celor doua liste (valorile cimpurilor "k" si "i" se citesc dintr-un fisier text) si inserarea elementelor listei a 2-a in prima lista conform algoritmului descris mai sus:

#include <stdlib.h>

#include <alloc.h>

#include <conio.h>

#include <stdio.h>

#include <math.h>

typedef struct list

plist

plist *p01,*p02,*p;

int q;

FILE *f;

void creare()

if (p2==NULL)

else

}

}

else

}

void insert(int a,int b)

if (p2==NULL)

else

void main()

while (p!=NULL);

p = p02;

printf(' Lista 2:n');

do

while (p NULL);

p = p02;

while (p!=NULL)

p = p01;

printf('Inregistrarile sortate sint:n');

do

while (p NULL);

Observatie:

Am folosit variabila "q" pentru a detecta faptul ca cele doua grupuri de inregistrari sunt si intre ele ordonate (adica ultima inregistrare din primul grup are cheia mai mica decit prima inregistrare a celui de-al doilea: Kn<=K'1).

O alta varianta de a interclasa doua liste este acea in care fiecare lista este considerata ca o sublista a unei liste unice de inregistrari. Trebuie introdus un cimp nou in cadrul unui element care sa indice faptul ca s-a terminat o sublista de inregistrari ordonate si incepe alta sublista de inregistrari ordonate. De asemenea, inregistrarile le vom lega intr-o lista dublu inlantuita cu structura urmatoare:

typedef struct listad

plistd;

unde cimpul 't' va avea valoarea +1 daca urmatorul element din lista este ordonat fata de cele anterioare, sau -1 daca incepe un nou sir de elemente ordonate.

Pentru a interclasa cele doua subliste, se procedeaza asemanator algoritmului precedent, numai ca de data aceasta se vor insera elementele sublistei a doua incepind cu ultimul element (indicat de pointerul 'p1') in sublista din stinga, care incepe cu elementul indicat de pointerul 'pp'. Procedeul continua pina cind elementul din stinga ultimului element inserat va avea valoarea -1 in cimpul 't'. In felul acesta, daca dupa fiecare inserare elementul respectiv este scos din sublista din dreapta, la sfirsit lista va contine aceleasi inregistrari ca si lista initiala, insa ordonate.

Un program pentru implementarea acestui algoritm este urmatorul:

#include <stdio.h>

#include <stdlib.h>

typedef struct listad

plist;

FILE *f;

plist *pp, *pu, *p;

int q, s, flag;

void creare(void)

void insertd(void)

else

pu = p1;

pu->right = NULL;

void test(void)

void main()

while (!(flag == 1));

printf('Inregistrarile sortate sint:n');

p = pp;

while (p != NULL)

Probleme propuse

1. Sa se sorteze, folosind algoritmul de interclasare de liste, mai multe liste de inregistrari.

2. Sa se sorteze , folosind un algoritm de interclasare de subliste, doua subliste inserind elementele sublistei din stinga in sublista din dreapta.

3. Sa se sorteze folosind un algoritm de interclasare de subliste un sir de inregistrari considerind fiecare subsir ordonat o sublista. Procedeul de interclasare se va aplica succesiv sublistei din stinga si sublistei din dreapta, pina cind se sorteaza toata lista. Cimpul 't' din structura unui element al listei dublu inlantuite va contine si valoarea '0' pentru ultimul element al listei ( folosit pentru detectarea sfisitului interclasarii).

4. 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 folosind interclasarea lor (in prealabil cele doua liste vor fi ordonate separat cu orice metoda de sortare).

5. Se cere sa se realizeze un program care efectueaza calculul mediilor candidatilor la un concurs de admitere ce consta din 3 probe, repartizarea 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 vor folosi 3 liste continind fiecare candidatii la un anumit profil, cele 3 liste se vor ordona crescator in ordinea mediilor si apoi se vor interclasa).

6. Se da o lista simplu inlantuita. Se imparte lista in subliste de cite 2 elemente, care se ordoneaza crescator (prin interschimbare) Se cere sa se interclaseze listele ordonate.

7. Aceeasi problema ca mai sus pentru lista dublu inlantuita.

8. Se dau 2 liste dublu inlantuite (se retin pointerii spre primul si ultimul element din lista). Una din liste este ordonata crescator, cealalta descrescator. Sa se interclaseze cele 2 liste intr-o lista ordonata crescator.

9. Folosind o stiva si o coada sa se conceapa un algoritm de interclasare.

10. Sa se interclaseze doua liste circulare ordonate in prealabil.

11. Sa se partitioneze o lista liniara dublu legata in subliste ordonate dupa care se interclaseaza aceste subliste.

12. Aceeasi problema ca mai sus, dar pentru liste liniare simplu legate.