Liste - Sortare prin inserare cu micsorarea decrementului (metoda lui O.L. Shell)

Liste - Sortare prin inserare cu micsorarea decrementului (metoda lui O.L. Shell)

In cadrul acestei metode, se presupune ca inregistrarile se afla toate pe mediul de intrare (de exemplu, disc magnetic). Ideea generala a acestei metode este aceea ca nu se sorteaza toate inregistrarile deodata, ci se impart pe grupuri care se sorteaza separat asamblindu-se dupa aceea in lista initiala.

Metoda a fost explicata de O.L.Shell pe un exemplu standard de 16 inregistrari.

La inceput se impart aceste inregistrari in 8 grupe a cite 2 elemente: (R1, R9), (R2, R10),,(R8, R16). Sortind fiecare grupa separat, se obtine o noua lista cu 16 inregistrari sortate partial (prima trecere).

La a doua trecere, se imparte lista in grupe de cite 4 elemente: (R1, R5, R9, R13) (R4 ,R8, R12, R16) si din nou fiecare sublista este sortata separat si reasamblata apoi in lista de 16 elemente. Urmatoarea trecere va sorta subliste de cite 8 inregistrari si le va reasambla, iar ultima trecere va sorta toate cele 16 inregistrari.

Fiecare din sublistele intermediare sunt fie relativ scurte, fie ordonate astfel ca sa se simplifice mult procesul de sortare ce poate utiliza insertia directa pentru acest proces. Inregistrarile tind sa convearga rapid catre ordinea lor finala.

Se observa ca 'distanta' intre elementele sublistelor de la prima trecere este 8, pentru a 2-a trecere va fi 4, pentru a 3-a trecere va fi 2, iar pentru ultima 1.

Aceasta secventa de incremente (8, 4, 2, 1) nu este obligatorie. Adica se poate utiliza orice secventa h_t, h_t-1,, h₂, h₁ cu conditia ca h₁=1 si h_t<n,

D. E. Knuth indica o secventa de incremente 'rezonabila':

h₁=1, h_t+1=3*h_{t +1} (1) sirul terminindu-se cind h_t+2>=n.

Pentru asamblarea elementelor in lista generala structura acestora in afara de cimpul de identificare si cel cu informatia utila, mai contine un singur cimp de legatura in lista:

typedef struct lists

*plists;

Dupa descompunerea listei in subliste, in vederea reasamblarii lor, acestea trebuie ordonate. Astfel pointerii de inceput ai fiecarei subliste sint inlantuiti intr-o alta lista, incit structura generala a sublistelor descompuse si inlantuite arata astfel:

Lista pentru legarea capetelor sublistelor descompuse contine elemente cu structura:

typedef struct slist

*pslist;

Variabila referinta 'pp' va contine adresa primului element al listei 'pslist', iar variabila referinta 'p0' va contine adresa primului element al listei asamblate 'plists'. Fiecare sublista se creeaza simultan cu ordonarea elementelor sale conform metodei insertiei directe. Sublista "k" se obtine incepind cu al k-lea element al listei 'plists', si apoi inserind in ea elemente aflate la distanta 'h' intre ele, pina cind lista se epuizeaza.

Reasamblarea sublistelor se face in modul urmator: - primul element al listei va fi primul element al primei subliste, al doilea element va fi primul element al celei de a 2-a subliste, procedeul continuind pina la primul element al ultimei subliste.

In mod analog se procedeaza cu al 2-lea element al fiecarei subliste, al 3-lea, etc., pina cind se epuizeaza toate elementele sublistei. Pentru determinarea incrementilor 'hi' conform relatiei (1), trebuie intii formata lista initiala, determinat numarul total "n" de inregistrari ce urmeaza sa fie sortate si numarul total de incrementi "k". Valoarea acestora se memoreaza in vectorul "h".

Cu acestea, putem descrie algoritmul de sortare intr-o forma generala astfel:

** Procedure SHELL

BEGIN

*creaza lista initiala a inregistrarilor;

*determina incrementii h₁,h₂,,h_k;

pentru i=k,1 executa

| p<---hi

| *descompune lista in liste ordonate (increment p)

| *recompune lista in subliste

END

Vom folosi trei proceduri in programul principal de sortare:

Procedura 'creare' ce va crea lista initiala a inregistrarilor, valorile cimpurilor 'k' si 'i' fiind citite dintr-un fisier text, si va determina numarul total de inregistrari.

Procedura 'desc' pentru descompunerea listei in subliste si ordonarea acestora. Aceasta procedura va folosi intermediar procedura 'insert' pentru crearea si ordonarea fiecarei subliste. Procedura 'desc' pentru incrementul 'p' al tabloului 'hi' va crea 'p' subliste, prima sublista incepind cu elementul 1 al listei generale, sublista 2 incepind cu elementul al 2-lea, , sublista 'p' incepind cu elementul al p-lea din lista initiala. Fiecare element al sublistelor se obtine din precedentul, 'sarind' peste 'p' elemente ale listei.

Procedura 'comp' realizeaza compunerea sublistelor in lista generala in maniera descrisa anterior. Se impune precizarea ca odata cu fiecare element al unei subliste introdus in lista generala, acesta va fi sters din sublista (si din memorie) astfel incit cimpul 'ps' al listei 'pslist' va contine tot timpul urmatorul element din sublista ce se va introduce in lista generala. De asemenea va fi sters din lista 'pslist' (si din memorie) si elementul care va indica (prin cimpul 'ps') spre o lista vida.

Programul de sortare folosind metoda micsorarii incrementului, care implementeaza algoritmul specificat anterior va fi:

#include <stdio.h>

#include <alloc.h>

#include <stdlib.h>

#define max 10

typedef struct lists

plists;

typedef struct slist

pslist;

plists *p, *p0;

pslist *pp;

FILE* f;

int h[max];

int i, l, k, n;

void creare()

void insert(plists **pp,int a,int b)

else

if (p1 == NULL)

else

if (p2 == NULL)

else

}

void desc()

p11 = p11->next;

}

void comp()

else

ps1 = ps2;

ps2 = ps2->pu;

}

void main()

while (!(h[i-1] >= n));

k = i - 1;

for (i = k; i >= 1; i--)

printf('Inregistrarile sortate sint:n');

p = p0;

do

while (!(p == NULL));

Probleme propuse

1. Intrucit operatiile cu sublistele structurii din fig.1. sunt proprii stivelor, sa se scrie programul de sortare al metodei lui SHELL, inlocuind sublistele cu stiva folosind proceduri pentru introducere si extragere a unui element din stiva.

2. Sa se scrie programul de sortare conform metodei lui SHELL folosind pentru lista 'slist' o lista circulara.

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 simplu inlantuita cu produsele societatii existente in stoc intr-o anumita zi.

b) Sa se ordoneze lista folosind sortarea prin metoda SHELL 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 ordoneze folosind metoda SHELL lista dupa numele si prenumele abonatilor, iar pentru abonatii cu acelasi nume dupa numerele lor de telefon.

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 (cu metoda SHELL) 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 care 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 folosind metoda SHELL astfel incit pentru fiecare teorema toate teoremele ce intra in demonstratia sa apara inaintea teoremei specificate.

7. 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 in raport cu ordinea lexicografica folosind o structura intermediara de tip arbore de cautare. Se vor parcurge doi pasi:

-inserarea elementelor celor doua liste intr-un arbore de cautare, initial vid. Elementele care se repeta vor fi inserate o singura data;

-construirea listei reuniune ordonata crescator folosind SHELL_SORT.

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.

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

10. 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, considerind ca ordinea importantei datelor referitoare la un oras (exceptind numele orasului) este cea precizata in enunt si sa se afiseze apoi lista ordonata (cu metoda SHEELL).

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

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