Algoritmi de Sortare Prin Numarare

INTRODUCERE

Cu toate ca dictionarele definesc "sortarea" ca un proces de separare si aranjare a lucrarilor dupa clase si fel , este traditional pentru programatorii de calculatoare sa utilizeze cuvantul intr-un sens mult mai special , de sortare a lucrurilor intr-o ordine ascendenta sau descendenta . Procesul , probabil , ar trebui numit " ordonare" si nu sortare; dar oricine incearca sa-i spuna ordonare va ajunge foarte curand in situatii foarte confuze , din cauza intelesurilor diferite atasate acestui cuvant .

Unii au sugerat ca termen "secventare" sa fie numele dat procesului de ordonare dar acest cuvant nu reda uneori sensul corect ,in mod special in cazul prezentei unor elemente egale . Este adevarat ca "sortare" este un cuvant foarte solicitat , dar este unanim acceptat in limbajul legat de calculatoare .

Cele mai importante aplicatii ale sortarii sunt :

a) solutionarea problemei legate de punerea impreuna a tuturor articolelor care au aceeasi identitate .

b) daca doua sau mai multe fisiere au fost sortate in aceeasi ordine , devine posibila gasirea intrarilor identice printr-o singura trecere prin ele , fara intoarceri inapoi . Sortarea face posibila utilizarea adresarii secventiale in fisiere mari , ca un substitut fezabil adresarii directe .

c) Sortarea este de asemenea un mijloc ajutator pentru cautare , permitand astfel ca iesirile de la calculator sa devina mai adecvate necesitatilor umane .

Cu toate ca sortarea a fost utilizata traditional in prelucrari de date cu caracter economic, ea este un mijloc de baza pe care programatorul trebuie sa o considere , pentru cele mai variate situatii .

Tehnicile de sortare asigura o ilustrare excelenta a ideilor generale legate de analiza algoritmilor , adica a ideilor utilizate pentru a determina performantele algoritmilor astfel incat sa se poata face un discernamant inteligent intre diferitele metode .

In lucrarea de fata este folosita o anumita terminologie pe ca o prezint in randurile ce urmeaza .

Se dau N articole R1 , … , RN care urmeaza a fi sortate ; ele vor fi numite inregistrari.

Intreaga colectie de N inregistrari va fi denumita fisier . Fiecare inregistrare R j , are o cheie Kj care guverneaza procesul de sortare . Poate exista si alta informatie in inregistrare in afara cheii ; aceasta informatie "satelit" nu va avea nici un efect asupra procesului de sortare , in afara faptului ca ea va ramane cu inregistrarea respectiva .

O alta relatie de ordonare "< " este specificata asupra cheilor , astfel , ca pentru orice valoare a celor trei chei a , b, c , urmatoarele conditii sa fie satisfacute :

1) Numai una din posibilitatile a< b , a=b , b<a este adevarata .

2) Daca a< b si b< c atunci a<c .

Aceste doua proprietati caracterizeaza conceptul matematic de ordonare liniara , denumita si ordonare totala . Orice relatie "< " ce satisface si (1) si (2) poate fi sortata prin majoritatea metodelor descrise in aceasta lucrare , cu toate ca unele tehnici de sortare vor necesita chei numerice sau alfabetice cu ordonarea obisnuita .

Lucrarea de fata este structurata in sasa capitole , care prezinta principalele tehnici de sortare interna folosite in programarea calculatoarelor . Prezentarea este insotita de numeroase exemple la fiecare capitol abordat , precum si de programe realizate pentru o mai buna fixare a tehnicilor de sortare respective .

Au fost inventate o multime de algoritmi de sortare. O idee buna consta in a studia caracteristicile fiecarei metode de sortare , astfel ca sa se poata efectua o alegere inteligenta in cazul aplicatiilor particulare. Pentru acest lucru trebuie sa se cunoasca terminologia de baza si notatiile ce vor fi utilizate in studiul sortarii .

Inregistrarile R1 , R2 , …, RN

Trebuie sortate in ordine crescatoare a cheilor K1 , K2 , …, KN , in principal prin descoperirea unei permutari p(1) p(2) …p(N) astfel incat

Kp(1) Kp(2) … Kp(N) .

Sortarea interna se refera la cazul in care numarul de inregistrari este suficient de mic pentru ca intreg procesul sa aiba loc in memoria interna a calculatorului .

Daca inregistrarile si /sau cheile necesita fiecare un numar destul de mic de cuvinte ale memoriei calculatorului atunci se recomanda construirea unui tabel cu adrese de legatura , ce indica inregistrarile , pentru a se putea manipula aceste adrese de legatura , in loc de inregistrarile voluminoase .

Aceasta metoda de sortare este denumita sortarea prin tabel de adrese .

Sortarea prin tabela de adrese

Daca cheia este scurta , dar informatia satelit a inregistrarii e lunga , cheia poate fi pusa impreuna cu adresele de legatura , pentru viteza mai mare , aceasta numindu-se sortare prin chei .

Alte tehnici de sortare utilizeaza un camp auxiliar de legatura care este inclus in fiecare inregistrare . Aceste inregistrari sunt astfel manipulate , incat in rezultatele finale , inregistrarile sa fie legate , astfel incat sa se formeze o lista liniara , cu fiecare legatura indicand inregistrarea urmatoare .

Aceasta metoda a fost denumita sortare de liste .

Sortare de liste

Dupa sortarea cu tabel de adrese sau prin metoda listelor , inregistrarile pot fi rearanjate in ordine crescatoare dupa dorinta . Exista mai multe cai de a face acest lucru , dar este nevoie de un spatiu de memorie suplimentar suficient pentru a inmagazina o inregistrare.

O alta alternativa consta in deplasarea inregistrarilor intr-un domeniu nou al memoriei , suficient pentru a inmagazina toate inregistrarile . Aceasta metoda este de doua ori mai rapida dar necesita un spatiu de memorie de aproape doua ori mai mare . In multe aplicatii nu este necesar sa se deplaseze deloc inregistrarile , deoarece campul de legatura este adecvat operatiilor de adresare ce urmeaza .

CAPITOLUL 1

SORTARE PRIN NUMARARE

COMPARARE PRIN NUMARARE

NUMARAREA DISTRIBUTIILOR

SORTARE PRIN NUMARARE

Aceasta metoda simpla se bazeaza pe ideea ca , cheia a (j-a) din secventa finala sortata este mai mare decat (j-1) din celelalte chei . Altfel spus , daca stim ca o anumita cheie este exact mai mare decat alte 27 de chei , inregistrarea corespunzatoare trebuie pusa in pozitia 28 dupa sortare . Deci ideea consta in compararea fiecarei perechi de chei, numa- rand cate vor fi mai mici decat fiecare cheie particulara .

Calea evidenta de a face comparatiile consta in

((compara Kj cu Ki) pentru 1jN) pentru 1iN

dar se poate vedea ca peste jumatate din aceste comparatii sunt redondate , deoarece nu este necesar de a compara cheile cu ele insele , si totodata nu va fi necesara compararea lui Ka cu Kb si apoi a lui Kb cu Ka . Deci vom avea nevoie numai de

(( compara Kj cu Ki ) pentru 1ji ) pentru 1iN .

Aceste considerente ne conduc la urmatorul algoritm.

1.1. Algoritmul de sortare prin numarare

Acest algoritm va sorta R1, …..,RN dupa cheile K1,……,KN prin intermediul unui tabel auxiliar COUNT [1],……, COUNT [N] pentru a numara cate chei vor fi mai mici decat o cheie data . Dupa terminarea algoritmului COUNT [j] + 1 va specifica pozitia finala a inregistrarii Rj .

Pasul 1 . [Sterge COUNT- urile ] . Pune COUNT [1] pana la COUNT [N] la zero .

Pasul 2. [ Cicleaza dupa i ] . Executa pasul 3 , pentru i = N , N-1 , ……., 2 ; apoi

termina algoritmul .

Pasul 3. [Cicleaza dupa j ] . Executa pasul 4 , pentru j = i-1, i-2, ……, 1 .

Pasul 4. [Compara Ki , Kj ] . Daca Ki<Kj , incrementeaza COUNT [j] cu 1 ; altfel

incrementeaza COUNT [i] cu 1 .

i =1 j = 0

Exemplu :

Acest algoritm nu comporta nici o deplasare de inregistrari . El este similar cu o sortare prin tabel de adrese , deoarece tabelul COUNT specifica aranjamentul final al inregistrarilor . Exista totusi o diferenta pentru ca COUNT [j] ne spune unde trebuie deplasat Rj , in loc de a indica care inregistrare trebuie deplasata in locul lui Rj .

Acest algoritm este foarte simplu , dar nu si foarte eficient deoarece pentru un numar de inregistrari N mare timpul de rulare este foarte mare .

Acesta se aplica mai ales in cazul in care exista multe chei egale si cand toate aceste chei sunt cuprinse in domeniul u Kj v unde ( vu) este mic . Aceste conditii par foarte restrictive , dar de fapt vom vedea multe aplicatii ale acestei idei , deoarece un fisier poate fi sortat partial daca se va aplica aceasta metoda digitilor anteriori cheilor , in loc de a o aplica la toata cheia .

Aceasta metoda de sortare a fost mentionata pentru prima oara de E.H.Friend in anul 1956 .

Program de sortare prin numarare

#include <conio.h>

#include <stdlib.h>

#include <stdio.h>

int n;

typedef arr[100] vector;

vector x, poz;

int n,i,nr;

void citire(vector x, int n)

{

for (int i=1; i < n; i++)

{

printf(“x[%d]=”,i);

scanf(“%d”,&x[i]);

}

}

void afisare(vector x,int n)

{

int i;

for (int i=1; i < n; i++)

printf(“%d”, x[i]);

}

void sortnum(vector x,int n)

{

int j;

vector y;

for (int j=1; j<n; j++)

{

nr=0;

for (int i=1; i<n; i++)

if (x[i]<=x[j])

inc(nr);

poz[j]=nr;

}

for (int i=1; i<n; i++)

y[poz[i]]=x[i];

for (int i=1; i<n; i++)

x[i]=y[i];

}

void main (void)

{

printf(“Dimensiunea vectorului este: “);

scanf(“%d”,&n);

printf(“Introduceti elementele distincte.”);

citire(x,n);

afisare(x,n);

sortnum(x,n);

afisare(x,n);

getch() ;

}

1.2.Algoritmul de sortare prin numararea distributiilor

Se considera ca toate cheile sunt intregi in domeniul u Kj v pentru 1 j N , acest algoritm va sorta inregistrarile R1, …., RN utilizand un tabel auxiliar

COUNT [u] …, COUNT [v] . La terminarea algoritmului , inregistrarile sunt deplasate intr-o zona de iesire S1,…, SN in ordinea dorita .

Pasul 1. [Sterge COUNT-urile.] Pune COUNT [u] pana la COUNT [v] la zero .

Pasul 2. [Cicleaza dupa j .] Executa pasul 3 pentru 1 j N ; apoi mergi la pasul 4.

Pasul 3. [Mareste COUNT [Kj]] . Incrementeaza valoarea lui [Kj] cu 1 .

Pasul 4.[Acumuleaza] (In acest moment COUNT [i] va fi egal cu numarul de chei ce

sunt egale cu i ). Pune COUNT [i] COUNT [i] + COUNT [i1] pentru

i=u+1,u+2,.. v.

Pasul 5. [Cicleaza dupa j .] ( In acest moment COUNT [i] va fi egal cu numarul de chei

care sunt mai mici ca , sau egale cu I ; in particular , COUNT[v] =N .)

executa pasul 6 pentru j= N , N1, …, 1 ; dupa care termina algoritmul .

Pasul 6. [Iesire Rj .] Pune i COUNT [Kj] ,

Si Rj si

COUNT[Kj] i1 .

j = 0

CAPITOLUL 2

SORTAREA PRIN INSERTIE

SORTARE PRIN INSERTIE DIRECTA

SORTARE PRIN INSERTIE BINARA SI INSERTIA IN DUBLU SENS

SORTARE CU MICSORAREA INCREMENTULUI. METODA LUI SHELL

INSERTIA DE LISTA

SORTARE PRIN CALCULARE DE ADRESE

1.1. INSERTIA DIRECTA

Sortarea cea mai simpla prin insertie este si cea mai evidenta .

Se considera 1< j N si inregistrarile R1 , …., Rj-1 aranjate astfel incat :

K1 K2 ….. Kj-1 , unde Kj s-a notat partea de cheie din Rj .

Se compara pe rand noua cheie Kj cu Kj-1 , Kj-2 , …., pana cand vom descoperi ca Rj trebuie inserat intre inregistrarile Ri+1 , …., Ri+1 ; apoi deplasam inregistrarile Ri+1 ,…., Rj+1 cu un spatiu si introducem noua inregistrare in pozitia

care sunt mai mici ca , sau egale cu I ; in particular , COUNT[v] =N .)

executa pasul 6 pentru j= N , N1, …, 1 ; dupa care termina algoritmul .

Pasul 6. [Iesire Rj .] Pune i COUNT [Kj] ,

Si Rj si

COUNT[Kj] i1 .

j = 0

CAPITOLUL 2

SORTAREA PRIN INSERTIE

SORTARE PRIN INSERTIE DIRECTA

SORTARE PRIN INSERTIE BINARA SI INSERTIA IN DUBLU SENS

SORTARE CU MICSORAREA INCREMENTULUI. METODA LUI SHELL

INSERTIA DE LISTA

SORTARE PRIN CALCULARE DE ADRESE

1.1. INSERTIA DIRECTA

Sortarea cea mai simpla prin insertie este si cea mai evidenta .

Se considera 1< j N si inregistrarile R1 , …., Rj-1 aranjate astfel incat :

K1 K2 ….. Kj-1 , unde Kj s-a notat partea de cheie din Rj .

Se compara pe rand noua cheie Kj cu Kj-1 , Kj-2 , …., pana cand vom descoperi ca Rj trebuie inserat intre inregistrarile Ri+1 , …., Ri+1 ; apoi deplasam inregistrarile Ri+1 ,…., Rj+1 cu un spatiu si introducem noua inregistrare in pozitia i+1 . Este convenabil sa se combine operatiile de comparare si de deplasare , intretesandu-le asa cum se va vedea si in algoritm . Deoarece Rj "intra in locul sau" aceasta metoda de sortare a fost numita si metoda de cernere si scufundare .

Algoritmul de sortare prin insertie directa

Inregistrarile R1 , …, RN sunt rearanjate pe locurile lor ; dupa sortare , cheile lor vor fi in ordinea K1 …. KN .

Pasul 1. [Cicleaza dupa j.] Executa pasii 2 pana la 5 , pentru j=2,3,….,N ; apoi termina

algoritmul.

Pasul 2. [Fixeaza i,K,R. ] Pune i j-1 , K Kj , R Rj . In pasii urmatori se va incerca

sa se insereze R in pozitia corecta , comparand K cu Ki pentru valori

descrescatoare a lui i .

Pasul 3. [Compara K , Ki . ]Daca K Ki , mergi la pasul 5 . (S-a gasit pozitia dorita

pentru inregistrarea R) .

Pasul 4. [Deplaseaza Ri , descreste i.] Pune Ri+1 Ri apoi i i-1 .Daca i0 , se merge

inapoi la pasul 3. (Daca i=0 , K va fi cea mai mica cheie gasita pana acum ,

astfel ca inregistrarea R apartine pozitiei 1) .

Pasul 5. [R in Ri+1 .] Pune Ri+1 R .

Exemplul 1 :

Exemplul 2 :

Program sortare prin insertie directa

#include <conio.h>

#include <stdlib.h>

#include <stdio.h>

int n;

typedef arr[100] sir;

sir x;

int i,j,n;

int aux;

typedef enum{true, false} boolean;

boolean term;

void insertie_directa(sir x,int n)

{

for (int i=2; i < n; i++)

{

j=i-1;

term=false;

aux=x[i];

do

{

if (x[j]>aux)

{

x[j+1]=x[j];

j=j-1;

}

else

term=true;

while ((j!=0) || (term==false))

x[j+1]=aux;

}

}

void citire(sir x, int n)

{

int i;

printf (“Introduceti numarul de elemente: ”);

scanf (“%d”, &n);

for (int i=1; i< n ; i++)

{

printf(“%d”,x[i]);

scanf(“%d”,&x[i]);

}

}

void afisare(sir x,int n)

{

int i;

printf (“Vectorul sortat este:”);

for (int i=1; i < n; i++)

printf(“%d”, x[i]);

}

void main (void)

{

printf(“ Introduceti dimensiunea vectorului:”)

scanf(“%d”,&n);

citire(x,n);

insertie_directa(x,n);

afisare(x,n);

getch() ;

}

2.2. INSERTIA BINARA SI INSERTIA IN DUBLU SENS

In timp ce a (j-a) inregistrare este prelucrata in timpul sortarii prin insertie directa , va trebui sa comparam cheia sa in medie cu aproximativ (1/2)j_din cheile sortate anterior. De aceea , numarul total de comparatii va fi in jur de (1/2)(1+2+……+N) (1/4)N², ceea ce devine foarte mare chiar in cazul valorilor modeste ale lui N .

Utilizand tehnicile de " cautare binara" care indica unde trebuie inserat al "j" -lea articol , numai dupa efectuarea log2 j de comparatii bine alese se va putea incepe inserarea . De exemplu : cand se va insera a 64 – a inregistrare , putem incepe comparand K64 cu K32 . Daca e mai mic il vom compara cu K16 , iar daca e mai mare cu K48 . Astfel locul inserarii lui R64 va fi cunoscut dupa efectuarea a numai 6 comparatii . Numarul total de comparatii pentru inserarea tuturor celor N articole va fi aproximativ Nlog2 N ceea ce va fi o imbunatatire fata de (1/4)N2 .

Acesta metoda a fost mentionata de John Mauchly in 1946 .

Pentru ca aceasta metoda de sortare se bazeaza pe "cautarea binara" vom prezenta pe scurt algoritmul de cautare binara .

Algoritmul de cautare binara

Fiind dat un tabel de inregistrari R1 , R2 ,…RN a caror chei sunt in ordine crescatoare

K1< K2 < …< KN , acest algoritm cauta inregistrarea cu cheia data K .

Pasul 1. [Initializare] . Se stabileste l←1 , u←N

Pasul 2.[Obtinere mijloc tabel] . In acest moment se cunoaste ca , daca K se gaseste

in tabel , el satisface Kl ≤ K ≤ Ku .( O formulare mai precisa a acestei situatii

se regaseste in exemplul de mai jos.) Daca u < l , algoritmul se termina fara

succes . In caz contrar , se stabileste i← [(l+u)/2] , mijlocul aproximativ al

tabelului .

Pasul 3. [Comparare.] Daca K<Ki , se trece la pasul 4; daca K>Ki , se trece la pasul

5 ; iar daca K=Ki , algoritmul se termina cu succes .

Pasul 4. [Ajustare u] . Se stabileste u←i-1 si se revine la pasul 2.

Pasul 5. [Ajustare l] . Se stabileste l←i+1 si se revine la pasul 2 .

3.Comparare

< = >

In exemplele pe care le prezintam mai jos , in primul caz se ilustreaza cautarea cheii 653 care se gaseste in tabel , iar al doilea caz se ilustreaza cautarea lui 400 , care nu se gaseste in tabel . Parantezele indica pe l si u , iar cheia subliniata reprezinta pe Ki . In ambele cazuri cautarea se termina dupa 4 comparatii .

a) Cautarea lui 653 :

b) Cautarea lui 400

Program cautare binara

//cautare binara intr-un vector sortat

#include <conio.h>

#include <stdlib.h>

#include <stdio.h>

int n;

typedef arr[100] vector;

vector v ;

const max=50;

n:1..max;

shortint x;

typedef enum{true, false} boolean;

boolean gasit;

procedure citire(vector v)

{

//citeste vectorul v ordonat crescator

i:1..max;

do

{

printf(“Dimensiunea vectorului = ”);

scanf(“%d“,&n);

}

while (n in [1..max])

printf(“\n Vectorul se da ordonat crescator”);

for (int i=1; i< n; i++)

{

printf(“v[%d]”,i);

scanf(“%d”,&v[i])

}

}

void caut_bin(shortint x,p,u)

{

//cauta numarul x in vectorul v de la pozitia p la pozitia u

shortint i;

while ((p<=u) && (!gasit))

{

i=(p+u) / 2;

//pozitia de mijloc in vectorul in care se cauta x

if (x==v[i])

{

printf (“%d se afla in vector la pozitia %d”,x,i);

gasit=true;

}

else

if (x<v[i])

u=i-1;

//daca x se afla la stanga jumatatii, se va cauta in prima

//jumatate

else p=i+1;

//daca x se afla la dreapta jumatatii, se va cauta in a

//doua jumatate

if (!gasit)

caut_bin(x,p,u);

}

}

void main (void)

{

citire(v);

printf (“Se cauta numarul “);

scanf(“%d”, &x);

gasit=false;

caut_bin(x,1,n);

if (!gasit)

printf(“%d nu se afla in vector', x);

getch();

}

Program sortare prin insertie binara

#include <conio.h>

#include <stdlib.h>

#include <stdio.h>

int n;

typedef arr[100] sir;

sir x ;

int i,j,n,inc,sf,med;

int aux;

void insertie_binara(sir x, int n)

{

for (int i=2; i < n; i++)

{

aux=x[i];

inc=1;

sf=i-1;

while (inc <= sf)

{

med=fabs((inc+sf)/2);

if (x[med] > aux)

sf=med-1

else

inc=med+1;

}

for (int j=i-1; j>inc; j–)

x[j+1]=x[j];

x[inc]=aux;

}

}

void citire(sir x, int n)

{

int i;

printf (“Introduceti numarul de elemente: ”);

scanf (“%d”, &n);

for (int i=1; i< n ; i++)

{

printf(“%d”,x[i]);

scanf(“%d”,&x[i]);

}

}

void afisare(sir x,int n)

{

int i;

printf (“Vectorul sortat este:”);

for (int i=1; i < n; i++)

printf(“%d”, x[i]);

}

void main (void)

{

printf(“ Introduceti dimensiunea vectorului:”)

scanf(“%d”,&n);

citire(x,n);

insertie_binara(x,n);

afisare(x,n);

getch();

}

Din nefericire, insertia binara , rezolva numai jumatate din problema . Dupa gasirea locului unde trebuie inserata inregistrarea Rj , va trebui sa deplasam aproximativ (1/2) j din inregistrarile sortate anterior pentru a face loc lui Rj , astfel incat timpul total de rulare sa ramana proportional cu N2 .

O varianta ce economiseste aproximativ din timpul de rulare fata de insertia binara obisnuita este insertia in dublu sens . Aici primul articol este pus in centrul unei zone de iesire ,iar pentru articolele ce urmeaza sa face spatiu prin depasarea de la stanga la dreapta ,dupa cum e mai convenabil .

Exemplu :

2.3. SORTARE CU MICSORAREA INCRERMENTULUI

METODA LUI SHELL

Daca avem un algoritm de sortare care deplaseaza articole cu cate o pozitie deodata timpul sau mediu de rulare va fi in cel mai bun caz proportional cu N2 , deoarece fiecare inregistrare trebuie sa "calatoreasca " in medie aproximativ (1/2)N2 pozitii , in timpul procesului de sortare . De aceea , daca vrem sa imbunatatim insertia directa , avem nevoie de un mecanism , prin intermediul caruia inregistrarile sa efectueze salturi lungi in loc de pasi mici .

O asemenea metoda a fost propusa de Donald Shell in 1959 si ea se numeste metoda de sortare cu micsorarea incrementului .

Algoritmul de sortare cu micsorarea incrementului

Inregistrarile R1 , …, RN sunt rearanjate pe loc ; dupa terminarea sortarii cheile vor fi in ordinea K1≤ …≤ KN . O secventa auxiliara de incrementi ht, ht-1 , …,h1 se utilizeaza pentru controlul procesului de sortare , unde h1=1 ; alegerea corecta a incrementilor poate micsora semnificativ timpul de sortare . Atunci cand t=1 algoritmul acesta de sortare se reduce la algoritmul de sortare prin insertie directa .

Pasul 1. [Cicleaza dupa s.] Executa pasul 2 pentru s=t , t-1, …,1;apoi termina algoritmul.

Pasul 2. [Cicleaza dupa j.] Pune h← hs si executa pasii 3→ 6, pentru h ≤ j ≤ N .(Se

utilizeaza metoda insertiei directe pentru a sorta elementele ce sunt la distante de

h pozitii , astfel incat Ki ≤ Ki+h pentru 1≤ i ≤ N-h . )

Pasul 3. [Fixeaza I , K , R .] Pune i← j-h , K← Kj , R← Rj .

Pasul 4. [Compara K, Ki .] Daca K≥ Ki ,mergi la pasul 6 .

Pasul 5. [Depaseaza Ri , descreste i . ] Pune pe Ri+h← Ri , apoi i← i-h .Daca I ≥ 0

mergi la pasul 4.

Pasul 6. [R in Ri+h .] Pune Ri+h ← R .

Exemplu : Sortare cu micsorarea incrementului (8 , 4 , 2 , 1)

La inceput se impart cele 16 inregistrari in 8 grupe de cate doua , adica (R1R9) ,

(R2 R10) , …, (R8 R16) .Sortand fiecare grupa separat , ne va conduce la o doua linie a tabelului , care se numeste "prima trecere" . Se observa ca 154 si-a schimat locul cu 512 ; 908 si 897 vor sari ambele in dreapta .

Acum vom imparti inregistrarile in 4 grupe de cate patru fiecare ,adica(R1 R5 R9 R13), …, (R4 R8 R12 R16 ) si din nou fiecare grup e sortat separat . Aceasta a "doua trecere" ne va conduce la linia 3 .

A treia trecere va sorta doua grupe de opt inregistrari , apoi a patra trecere termina treaba sortand toate cele 16 inregistrari .

Fiecare din procesele intermediare de sortare , implica fie un fisier relativ scurt , fie un fisier bine ordonat , astfel ca insertia directa poate fi utilizata pentru fiecare operatie de sortare . Inregistrarile tind sa convearga rapid spre destinatia lor finala .

Secventa 8,4,2,1 nu este obligatorie ; poate fi utilizata orice secventa ht , ht-1 , …, h1, cu conditia ca ultimul increment h, sa fie egal cu 1 .

Timpul de rulare pentru acest algoritm de sortare cu micsorarea incrementului este O(N3/2) cand h =2s ─1 , 1≤ s≤ t =[log2N] .

2.4. INSERTIA DE LISTA

Una din caile generale cele mai importante pentru a imbunatatii un algoritm ,

consta in examinarea atenta a structurii sale de date , deoarece reorganizarea structurii de date astfel incat sa se evite operatii redondante , conduce des la imbunatatiri substantiale .

Insertia directa implica doua operatii de baza :

a) parcurgerea unui fisier ordonat pentru a gasi cea mai mare cheie , mai mare sau

egala unei chei date .

b) inserarea unei inregistrari noi intr-o anumita parte a fisierului ordonat .

Fisierul este o lista liniara si algoritmul de insertie directa va manipula aceasta lista utilizand alocarea secventiala .De aceea va fi necesar sa se deplaseze aproximativ jumatate din inregistrari pentru a efectua fiecare operatie de insertie . Pe de alta parte , stim ca alocarea cu legaturi , este ideala pentru insertie , deoarece trebiue schimbate numai cateva legaturi . Cealalta operatie , parcurgerea secventiala , este la fel de usoara in cazul alocarii cu legaturi , ca si in cazul alocarii secventiale . Sunt necesare numai legaturi unidirectionale deoarece parcurgerea listei are loc intotdeauna in aceeasi directie.

Deci , structura de date pentru insertie directa este o lista cu legaturi , unidirectionala.

Este indicat ca lista sa fie parcursa in ordine crescatoare .

Algoritmul de insertie de lista

Se considera ca inregistrarile R1 ,…, RN contin cheile K1 ,…, KN si "campurile de legatura" L1 ,….,LN capabile de a contine numere de la 0 la N.

Exista un camp de legatura L0 intr-o inregistrare artificiala K0 la inceputul fisierului . Algoritmul va fixa campurile de legatura astfel incat inregistrarile sa fie legate in ordine ascendenta . Astfel , daca p(1), …, p(N) este permutarea stabila care face Kp(1),…,Kp(N) acest algoritm va da :

L0=p(1); Lp(i) =p(i+1) , pentru 1≤ i ≤ n ; Lp(N) =0 .

Pasul 1. [Cicleaza dupa j]. Pune L0 ←N , LN←0 (L0 actioneaza in calitate de "cap" al

listei , iar 0 in calitate de legatura zero , deci lista este circulara) . Executa pasii

de la 2 la 5 pentru j = N-1 , N-2 , …….., 1 ; apoi termina algoritmul .

Pasul 2. [Fixeaza p , q , K] . Pune p← L0 , q ← 0 , K ← Kj . (In pasii ce urmeaza vom

insera Rj la locul potrivit in lista legata , comparand K cu cheile anterioare in

ordine ascendenta . Variabilele p si q au rol de indicatoare spre locul curent in

lista , cu p = Lq astfel ca q este cu un pas in urma lui p .)

Pasul 3. [Compara K cu Kp] . Daca K ≤ Kp mergi la pasul 5 . (Am gasit pozitia dorita

pentru inregistrarea R , intre Rq si Rp in lista) .

Pasul 4. [Impinge p , q] . Pune q←p , p← Lq . Daca p > 0 , mergi inapoi la pasul 3 .

(Daca p = 0 , K va fi cheia cea mai mare gasita pana in prezent , deci

inregistrarea R apartine sfarsitului listei , intre Rq si R0 ) .

Pasul 5. [Insereaza in lista]. Pune Lq← j , Lj ← p .

Acest algoritm este important nu numai pentru ca prezinta o metoda de sortare simpla , dar si pentru ca apare des ca o componenta a altor algoritmi de prelucrare a listelor .

Exemplu de insertie de lista :

Algoritmul de sortare directa este un algoritm simplu si natural , care face ≈ (1/4)N² comparari si (1/2)N² deplasari . Acest algoritm a fost imbunatatit in cazul insertiei binare care face ≈ N log2 N comparatii si (1/4)N² deplasari . Tehnica lui Shell , de "micsorare a incrementului" reduce numarul de comparatii si deplasari la N1/3 , in cazul lui N in domeniul practic posibil . Pe masura ce N → ∞ acest numar poate fi micsorat la N(log2 N)2 . O alta metoda de a imbunatati algoritmul de sortare directa , utilizand o structura de date legata , ne-a dat metoda insertiei de liste care necesita aproximativ (1/4)N2 comparatii , 0 deplasari si 2N schimburi de legaturi .

2.5. SORTARE PRIN CALCUL DE ADRESE

Sortarea prin calcul de adrese necesita spatiu aditional de memorie proportional cu N, pentru care sa nu fie necesare deplasari excesive , sau pentru a forma tabele auxiliare care vor ajuta in tinerea evidentei neregularitatilor din distributia cheilor . Putem sa utilizam cel mai bine aceste spatii de memorie , daca le alocam campurilor de legatura , ca in metoda insertiilor de liste . Aceasta cale permite evitarea necesitatii de zone diferite pentru intrare si iesire . Totul poate fi facut in aceiasi zona de memorie .

Ideea de baza consta in generalizarea insertiei de liste astfel incat sa existe mai multe liste in loc de una . Fiecare lista este utilizata pentru un anumit domeniu de chei . Se considera ipoteza in care distributia cheilor este egala fata de cazul "aglomerarilor" nere- gulate . Multimea valorilor posibile ale cheilor va fi partitionata in M parti . Vom consi-dera ca 1/M este probabilitatea ca o cheie data sa apartina uneia din partitii . Apoi , vom asigura memorie pentru M capete de lista si vom mentine fiecare lista ca la insertia simpla de liste .

Pentru a ilustra metoda , fie cele 16 chei utilizate in exemplu , impartite in M = 4 domenii 0-249 , 250-499 , 500-749 , 750-799 . Vom obtine urmatoarea configuratie pe masura ce sortarea avanseaza :

CAPITOLUL 3

SORTAREA PRIN INTERSCHIMBARE

Procesul de insertie directa poate fi vizualizat ca o metoda de interschimbare : fiecare inregistrare Rj o vom interschimba cu vecinii sai din stanga , pana cand va ajunge la locul potrivit . Metodele de sortare prin interschimbare se clasifica in :

a) Sortare cu interschimbare si selectie (metoda bulelor);

b) Sortare cu interclasare si interschimbare (sortarea paralela Batcher);

c) Sortarea cu interschimbarea partitiilor (sortarea rapida a lui Hoare);

d) Sortarea dupa ranguri cu interschimbare.

Caracterisitca dominanta a celor patru metode de sortare este interschimbarea .

3.1. SORTARE PRIN METODA BULELOR

Cea mai evidenta cale de sortare prin interschimbare consta in compararea lui K1 cu K2 si interschimbarea lui R1 cu R2 , daca cheile nu sunt in ordine , apoi se va face acelasi lucru pentru inregistrarile R2 si R3 , R3 si R4 , e.t.c. . in timpul acestei secvente de operatii , inregistrarile cu chei mari tind sa se deplaseze spre dreapta , si de fapt inregis-trarea cu cheia cea mai mare va avansa pentru a deveni RN . Repetarea acestui proces va pune inregistrarile potrivite in pozitiile RN-1 , RN-2 , e.t.c. astfel incat toate inregistrarile vor fi sortate .

Metoda e denumita "sortare prin metoda bulelor " deoarece elementele mari "se ridica ca niste bule" in pozitia lor corespunzatoare , in contrast cu sortarea prin insertie directa in care elementele "se cufunda " la un nivel corespunzator .

Algoritm de sortare prin metoda bulelor

Inregistrarile R1 ,……, RN sunt rearanjate ; dupa terminarea sortarii , cheile vor fi in ordine , K1 ≤ ….≤ KN .

Pasul 1. [Initializeaza BOUND]. Stabileste BOUND ← N . (BOUND este indicele cel

mai mare pentru care inregistrarea nu se cunoaste a fi in pozitia finala ; astfel , se

indica faptul ca la acest punct nimic nu este cunoscut).

Pasul 2. [Cicleaza pe j] . Stabileste pe j ← 0 . efectueaza pasul 3 pentru j = 1,2,3, …….. ,

BOUND -1 , si apoi mergi la pasul 4.

Pasul 3.[Compara / interschimba Rj : Rj+1]. Daca Kj > Kj+1 , interschimba Rj ↔ Rj+1 si

stabileste t ← j .

Pasul 4. [Sunt interschimbari?] . Daca t = 0 , algoritmul se termina. In caz contrar

stabileste BOUND ← t si revino la pasul 2 .

Nu

Exemplu

Dupa fiecare trecere prinn fisier toate inregistrarile superioare , inclusiv ultima care se shimba, trebuie sa se gaseasca in pozitia lor finala ,astfel incat sa nu mai fie necesara examinarea lor,la trecerile urmatoare.La trecerea finala nu se executa nici un interschimb

Program sortare prin metoda bulelor

#include <conio.h>

#include <stdlib.h>

#include <stdio.h>

int n;

typedef arr[100] sir;

sir x ;

int i,n,ld;

int aux;

void bule(sir x, int n)

{

ld=n-1;

do

{

for (int i=1; i < ld; i++)

{

if (x[i]>x[i+1])

{

aux=x[i];

x[i]=x[i+1];

x[i+1]=aux;

} ld:=ld-1;

while (ld != 0)

}

void citire(sir x, int n)

{

int i;

printf (“Introduceti numarul de elemente: ”);

scanf (“%d”, &n);

for (int i=1; i< n ; i++)

{

printf(“%d”,x[i]);

scanf(“%d”,&x[i]);

}

}

void afisare(sir x,int n)

{

int i;

for (int i=1; i < n; i++)

printf(“%d”, x[i]);

}

void main (void)

{

printf(“ Introduceti dimensiunea vectorului:”)

scanf(“%d”,&n);

citire(x,n);

bule(x,n);

afisare(x,n);

getch();

}

SORTAREA PRIN METODA BULELOR OPTIMIZATA

Comparata cu insertia directa , sortarea prin metoda bulelor implica un program mai complicat si necesita un timp de doua ori mai lung . De aceea exista o alta varianta care perfectioneaza sortarea prin metoda bulelor si care se bazeaza pe faptul ca se poate sesiza momentul de la care vectorul este ordonat .

Program sortare prin metoda bulelor optimizata

#include <conio.h>

#include <stdlib.h>

#include <stdio.h>

int n;

typedef arr[100] sir;

sir x ;

int i,n,ld;

int aux;

int um;

void buleopt(sir x, int n)

{

ld=n-1;

do

{

um=0;

for (int i=1; i < ld; i++)

{

if (x[i]>x[i+1])

{

aux=x[i];

x[i]=x[i+1];

x[i+1]=aux;

um=i;

}

ld=um-1;

while (um!=0)

}

void citire(sir x, int n)

{

int i;

printf (“Introduceti numarul de elemente: ”);

scanf (“%d”, &n);

for (int i=1; i< n ; i++)

{

printf(“%d”,x[i]);

scanf(“%d”,&x[i]);

}

}

void afisare(sir x,int n)

{

int i;

for (int i=1; i < n; i++)

printf(“%d”, x[i]);

}

void main (void)

{

printf(“ Introduceti dimensiunea vectorului:”)

scanf(“%d”,&n);

citire(x,n);

buleopt(x,n);

afisare(x,n);

getch();

}

3.2. SORTARE PRIN INTERSCHIMBARE SI INTERCLASARE . METODA PARALELA A LUI BATCHER

Daca se doreste un algoritm de interschimbare al carui timp de rulare sa fie mai mare decat N2 va fi necesar sa se selecteze anumite perechi de chei (Ki , Kj) , neadiacente , pentru comparatie . In caz contrar vor fi necesare tot atatea interschimbari , cate inversari poseda permutarea initiala , iar numarul mediu de inversari este (1/4)(N2 – N) .

In 1964 K.E. Batcher examinand interschimbarile potentiale ale unei secvente de comparatii , a elaborat o metoda de programare care necesita o demonstratie speciala pentru a se arata ca este corecta , deoarece au loc relativ putine comparatii .

Metoda de sortare a lui Batcher este asemanatoare cu metoda lui Shell cu deosebirea ca efectuarea comparatiilor se face intr-un mod nou astfel incat nu mai este necesara propagarea interschimbarilor . deoarece algoritmul lui Batcher interclaseaza in esenta perechi a unor subsecvente sortate , el poate fi numit sortare prin interschimbare si interclasare .

Algoritmul de intershimbare si interclasare

Inregistrarile R1 , ….., RN sunt rearanjate ; dupa terminarea sortarii cheile lor vor fi in ordine , K1 ≤ …. ≤ KN . Presupunem ca N ≥ 2 .

Pasul 1. [Initializeaza p]. Stabileste p ← 2t-1 , unde t = [log2 N] reprezinta cel mai mic

intreg , astfel incat 2t ≥ N . (Pasii 2 pana la 5 vor fi efectuati pentru p = 2t-1 , 2t-2,

……, 1).

Pasul 2. [Initializeaza q , r, d]. Stabileste q ← 2t-1 , r ← 0 , d ← p .

Pasul 3. [Cicleaza pe i]. Pentru toti i astfel incat 0 ≤ i < N-d si i ۸ p = r se executa pasul

4. Apoi mergi la pasul 5 .(Aici i ۸ p constituie "produsul logic" al reprezenta-

rilor binare ale lui i si p; fiecare bit al rezultatului este zero cu exceptia acelora

unde i si p au ambii 1 in pozitiile corespunzatoare . Astfel 13 ۸ 21 = (1101)2 ۸

(10101)2 = (00101)2 =5 . In acest moment , d este multiplu impar de p iar p este

o putere a lui 2 , astfel incat i ۸ p ≠ (i+d) ۸ p ; rezulta ca activitatile pentru pasul

4 pot fi efectuate pentru toti i , in orice ordine , chiar simultan ).

Pasul 4. [Compara / interschimba Ri+1 : Ri+d+1]. Daca Ki+1 > Ki+d+1 , interschimba

Ri+1↔Ri+d+1 .

Pasul 5. [Cicleaza pe q]. Daca q ≠ p , stabileste d ← q-p , q ← q/2 , r← p , si se revine la

pasul 3 .

Pasul 6. [Cicleaza pe p]. (La acest punct permutarea K1 , K2 , ….. ,KN este ordonata dupa

p) . Stabileste p ← [p/2] . Daca p > 0 mergi inapoi la pasul 2 .

Algoritmul sorteaza N elemente prin sortarea lui R1 , R3 , R5 , … si R2 , R4 , R6 , ….., independent; apoi executa pasii 2 pana la 5 pentru p = 1 in vederea interclasarii celor doua secvente . Acest algoritm are o particularitate remarcabila : toate comparatiile / interschimbarile specificate de catre o iteratie data pentru pasul 3, pot fi efectuate simultan , in calculatoarele sau retelele logice , care permit calcule paralele . Cu aseme-nea operatii paralele , sortarea este terminata in (1/2)[log2 N] ([log2 N] +1) pasi .

Exemplu:

3.3.SORTAREA RAPIDA

Secventa de comparatie in metoda lui Batcher este predeterminata ; de fiecare data se compara aceeasi pereche de chei , indiferent de experienta acumulata despre fisier , din comparatiile anterioare . Desi algoritmul de sortare prin metoda bulelor utilizeaza in mod limitat informatiile anterioare pentru a reduce volumul de munca la sfarsitul fisierului , acelasi lucru , in principal , este valabil si pentru sortarea prin metoda bulelor .

Sortarea rapida abordeaza o noua strategie , complet diferita , care foloseste rezultatele fiecarei comparatii pentru a stabili care sunt cheile care urmeaza a fi comparate . O asemenea strategie nu e adecvata calculatoarelor paralele dar poate fi

folosita cu succes in calculatoarele care lucreaza serial .

Se considera urmatoarea schema comparatie / interschimb :

Se utilizeaza doi indicatori i si j , cu i = 1 si j = N , initial . Se compara Ki :Kj , si daca nu este necesar interschimbul se micsoreaza j cu 1 , repetandu-se procesul . Daca apare un interschimb , se mareste i cu 1 si se continua compararea , marind i pana la aparitia unui nou interschimb . Apoi se micsoreaza din nou j , continuand-se in acelasi mod pana cand i = j .

Algoritmul de sortare prin interschimb de partitii

Inregistrarile R1 ,…, RN sunt rearanjate pe loc; dupa terminarea sortarii cheile lor vor fi in ordine K1, …, KN . Pentru memorarea temporara este necesara o stiva cu cel mult log2N intrari . Acest algoritm urmeaza procedura de sortare rapida prin partitii , cu usoare modificari pentru marirea eficientei .

a) Presupunem prezenta cheilor artificiale

K0 =─ ∞ si KN+1= + ∞ astfel incat

K0 ≤ Ki ≤ KN+1 pentru 1≤i≤N .

b) Subfisierele lui M , sau un numar redus de elemente , sunt sortate prin insertie

directa , unde M ≥ 1 este un parametru care trebuie ales dupa cum se descrie mai

jos in text

c) Pe durata unei etape particulare sunt efectuate una sau doua comparatii suplimen-

tare (permitand indicatorilor i , j sa se intersecteze) astfel incat buclele principale

de comparare pot fi oricat de rapide

d) Inregistrarile cu chei egale sunt interschimbate , desi nu este strict necesar (ajuta

sectionarea subfisierelor pe jumatate , atunci cand sunt prezente un numar egal de

elemente).

Pasul 1. [Initializeaza.] Stabileste stiva vida , si l← 1, r ← N .

Pasul 2. [Incepe o noua etapa.] (Acum dorim sa sortam subfisierele de la Rl , ….. ,Rr ;

conform naturii algoritmului avem r ≥ l-1 si Kl-1 ≤ Ki ≤ Kr+1 pentru l ≤ i ≤ r).

Daca r-l<M mergi la pasul 8. In caz contrar i ← l , j← r , K ← Kl , R ← Rl .

Pasul 3. [compara K : Kj .] Daca K < Kj micsoreaza j cu 1 si repeat acest pas .

Pasul 4. [Transfer la Ri .] (La acest punct Ki este o cheie nesemnificativa ≥ K si K ≥ Kj )

Daca j ≤ i , stabileste Ri ← R si mergi la pasul 7 . In caz contrar stabileste

Ri←Rj si mareste i cu 1.

Pasul 5. [Compara Ki : K.] Daca Ki < K mareste i cu 1si repeta acest pas .

Pasul 6. [Transfer la Rj .] (La acest punct Kj este o cheie nesemnificativa ≤ K , si K ≤ Ki)

Daca j ≤ i , stabileste Rj ← R si i ← j . In caz contrar Rj ← Ri , micsoreaza j cu

1 si mergi la pasul 3 .

Pasul 7. [Pune in stiva .] (Acum subfisierul Rl … Ri … Rr a fost partitionat astfel incat

Kk ≤ Ki pentru l ≤ K ≤ i si Ki ≤ Kk pentru i ≤ k ≤ r .) Daca r-i ≥ i-l , plaseaza

(i+1 , r) in varful stivei si stabileste R ← i-1 . In caz contrar , plaseaza (l , i-1)

in varful stivei si stabileste l ← i+1 . (Fiecare intrare (a , b) in stiva reprzinta o

cerere de sortare a subfisierului Ra … Rb la un anumit timp in viitor.) Acum

mergi inapoi la pasul 2

Pasul 8. [Sortare prin insertie directa.] Pentru j = l+1 , l+2 , … , pana la j > r , efectueaza

urmatoarele operatii : stabileste K←Kj , R←Rj , i←j-1; apoi stabileste Ri+1←Ri ,

i←i-1 , de zero sau mai multe ori pana cand Ki > K ; apoi stabileste Ri+1←R .

Pasul 9. [Anuleaza stiva.] Daca stiva este vida sortarea s-a efectuat ; in caz contrar

inlatura intrarea ei din varf (l' , r') , stabileste l←l' , r← r' si treci inapoi la

pasul 2 .

Exemplu :

Fisierul din exemplul dat este sortat prin aceasta metoda in 11 etape . parantezele in- dica acele subfisiere care trebuie sa mai fie sortate si care pot fi reprezentate prin doua variabile l si r. De fiecare data cand fisierul este divizat , se plaseaza sub fisierul cel mai mare in stiva si se incepe lucrul cu celalalat pana cand se obtin fisiere extrem de scurte , stiva necontinand mai mult de circa log 2 N intrari .

Program de sortare rapida

#include <conio.h>

#include <stdlib.h>

#include <stdio.h>

int n;

typedef arr[100] vector;

vector x ;

int k,n;

void citire(vector x, int n)

{

int i;

for (int i=1; i< n ; i++)

{

printf(“%d”,x[i]);

scanf(“%d”,&x[i]);

}

}

void afisare(vector x,int n)

{

int i;

for (int i=1; i < n; i++)

printf(“%d”, x[i]);

}

void poz(vector x, int s, int d, int k)

{

int i,j,i1,j1,aux,c;

i=s;

j=d;

i1=0;

j1=-1;

while (i < j)

{

if (x[i]>x[j])

{

aux=x[i];

x[i]=x[j];

x[j]=aux;

c=i1;

i1=-j1;

j1=-c;

}

i=i+i1;

j=j+j1;

}

k=i;

}

void quick(vector x,int s,d)

{

if (s < d)

{

poz(x,s,d,k);

quick(x,s,k-1);

quick(x,k+1,d);

}

}

void main (void)

{

printf(” Dimensiunea vectorului: ”);

scanf(“%d”,&n);

citire(x,n);

afisare(x,n);

quick(x,1,n);

afisare(x,n);

}

3.4. SORTAREA DUPA RANGURI CU INTERSCHIMB

Este o metoda de sortare care difera foarte mult de cele prezentate anterior deoarece ea utilizeaza reprezentarea binara a cheilor , asfel incat ea este indicata numai pentru calculatoarele binare . In loc de a compara doua chei intre ele aceasta metoda inspecteaza bitii separati ai cheilor pentru a vedea daca sunt 0 sau 1 . Deoarece depinde de reprezentarile in baza 2 ea se poate numi "sortare dupa baza cu interschimb" sau"sortare dupa ranguri cu interschimb".

Algoritmul implica doua etape importante :

a) Sorteza secventa dupa bitul cel mai semnificativ , asfel incat toate cheile care incep cu 0 vor veni inaintea tuturor cheilor care incep cu 1. Aceasta sortare este realizata prin gasirea cheii Ki plasata cat mai la stanga si care incepe cu 1, precum si a cheii Kj , plasata cel mai la dreapta si care incepe cu 0 . Apoi Ri si Rj sunt interschimbate , iar procesul se repeta pana cand i > j .

b) Fie F0 elementele care incep cu bitul 0 si fie F1 celelalte elemente . Se aplica metoda sortarii dupa ranguri cu interschimb lui F0 (incepand acum cu bitul secund din stanga , in locul primului bit mai semnificativ) , pana cand F0 este complet sortat ; apoi se efectueaza acelasi lucru pentru F1 .

Algoritm de sortare dupa ranguri cu interschimb

Inregistrarile R1, … , RN sunt rearanjate pe loc ; dupa terminarea sortarii , cheile lor vor fi in ordine K1 , … , KN . Presupunem ca fiecare cheie este un numar binar cu m biti , de exemplu (a1 , a2 , … , am)2 ; cel de-al i-lea bit semnificativ , ai , se numeste bitul 'i' al cheii . O stiva auxiliara cu spatiu pentru cel mult m-1 intrari va fi necesara pentru o memorare temporara .

Pasul 1. [Initializeaza .] Stabileste stiva vida si l1← 1 , r ← N , b ← 1.

Pasul 2. [Incepe o noua etapa .] (Acum se doreste sortarea subfisierului Rl ≤ … ≤ Rr cand

avem l ≤ r dupa bitul b .) Daca l = r se merge la pasul 10 . in caz contrar i ← l ,

j ← r .

Pasul 3. [Inspecteza Ki pentru 1.] Examinaeza bitul b din Ki . Daca este 1 , se merge la

pasul 6 .

Pasul 4. [Mareste i.] Mareste i cu 1 . Daca I ≤ j , se trece la pasul 3 ; in caz contrar se

merge la pasul 8 .

Pasul 5. [Inspecteza Kj+1 pentru 0 .] Examineaza bitul b din Kj+1 . Daca este 0 se merge la

pasul 7 .

Pasul 6. [Micsoreaza j.] Micsoreza j cu 1. Daca i ≤ j se trece la pasul 5 ; in caz contrar se

merge la pasul 8 .

Pasul 7. [Interschimba Ri , Rj+1.] Interschimba inregistrarile Ri ↔ Rj+1 ; apoi se merge la

pasul 4 .

Pasul 8. [Test pentru cazuri speciale.] (In acest moment a fost terminata o etapa de

partitionare ; i = j+1 , bitul b al cheilor Kl , … , Kj este 0 , iar bitul b al cheilor

Kj , … , Kr este 1.) Se incrementeaza b cu 1 . Daca b > m , unde m este numarul total de biti in chei se merge la pasul 10 . (In asemenea caz subfisierul Rl … Rr a fost sortat . Acest test nu trebuie facut daca nu exista sansa de a avea prezente chei egale in fisier .) In caz contrar , daca j < 1 sau j = r , se merge inapoi la pasul 2 (toti bitii examinati au fost 1 sau 0). In cazul in care j = l se mareste l cu 1 si se merge la pasul 2 (a existat un singur bit 0) .

Pasul 9. [Plaseaza in stiva .] Se introduce intrarea (r , b) in varful stivei ; apoi se stabile-

ste r← j si se merge la pasul 2.

Pasul 10. [Extrage din stiva .] Daca stiva este vida , sortarea s-a terminat ; in caz contrar

se stabileste l ← r+1 , se inlatura intrarea (r' , b') din varful stivei , se stabileste

r ← r' , b ← b' si se merge la pasul 2 .

Exemplu :

In tabelul prezentat pe pagina urmatoare se arata modul in care actioneaza sortarea dupa ranguri cu interschimb pe secventa de 16 numere aleatoare , care a fost convertita in octal .

Etapa 1 din tabel arata intrarea initiala , iar dupa interschimbul dupa primul bit se va ajunge la etapa 2 .

Etapa 2 sorteaza primul grup dupa bitul 2 iar etapa 3 actioneaza asupra bitului 3 .

(Trebuie sa se faca conversia din octal in zecimal )

Cand se ajunge la etapa 5 , dupa sortarea pe baza bitului 4 se observa ca fiecare grup ramas mai are cate un singur element , astfel incat aceasta portiune a fisierului nu trebuie sa fie examinata in continuare .

Notatia "4[0232 0252]" semnifica faptul ca subfisierul 0232 0252 asteapta sa fie sortat dupa bitul 4 de la stanga . In acest caz particular nu se realizeaza nici un progres , cand se sorteaza dupa bitul 4 ; trebuie sa se mearga la bitul 5 inainte ca obiectele sa fie separate .

Procesul complet de sortare prezentat in tabel necesita 22 de etape , iar numarul total de interschimbari este 17 .

Ca si in sortarea rapida si aceasta metoda utilizeaza o stiva pentru a tine evidenta in legatura cu "linia de demarcatie a informatiei " pentru subfisierele aflate in asteptare .

In loc de a sorta initial cel mai mic subfisier , este mai convenabil sa se mearga de la stanga la dreapta deoarece , in acest caz dimensiunea stivei nu poate depasi niciodata numarul de biti din cheile sortate . Intrarea (r , b) in stiva este folosita pentru a indica limita dreapta a unui subfisier care asteapta sa fie sortat dupa bitul b; limita stanga b este implicita datorita naturii stanga – dreapta a procedurii .

CAPITOLUL 4

SORTARE PRIN SELECTIE

SORTAREA PRIN SELECTIE

O alta familie importanta de tehici de sortare e bazata pe ideea selectiei repetate . Cea mai simpla metoda de selectie se bazeaza pe urmatoarele :

a) Aflati cheia cea mai mica ; transferati inregistrarea corespunzatoare in aria de iesire si apoi inlocuiti cheia prin valoarea ∞ (care se presupune ca e mai mare decat orice cheie actuala )

b) Repetati pasul a) , de aceasta data fiind selectata urmatoarea cheie cu valoarea cea mai mica , deoarece cea mai mica cheie a fost inlocuita prin ∞ .

c) Continuati repetarea punctului a) cele N inregistrari au fost selectate .

O astfel de metoda de selectie necesita ca toate elementele de intrare sa fie prezentate inainte ca sortarea sa poata incepe si ea genereaza datele finale de iesire , una dupa alta in secvente . Aceasta metoda se deosebeste de insertie deoarece in sortarea prin insertie intrarile se primesc secvential , dar nu se stie nimic despre iesiri , pana cand sortarea nu este completa.

Metoda de sortare prin selectie implica N-1 comparatii de fiecare data cand o noua inregistrare este selectata si de asemenea , necesita un spatiu separat de memorie pentru datele de iesire . Acaesta situatie se poate ameliora evitand utilizarea lui ∞ . Se poate lua valoarea selectata si muta intr-o pozitie adecvata ei , prin interschimbarea ei cu inregistra- rea curenta care ocupa aceea pozitie . Apoi nu mai este necesar sa consideram aceasta pozitie in selectiile viitoare .

4.1. SORTAREA PRIN SELECTIE DIRECTA

Aceasta metoda se bazeaza pe cele expuse anterior cu exceptia faptului ca e mai convenabil sa se selecteze la inceput elementul cel mai mare , apoi al doilea element cu valoarea cea mai mare si asa mai departe .

Algoritmul de sortare prin selectie directa

Inregistrarile R1 , … , RN trebuie sortate ; dupa ce sortarea este completa cheile acestor inregistrari vor fi in ordine , K1 ≤ … KN .

Pasul 1. [Bucleaza pe j.] Se executa pasii 2 si 3 pentru j = N , N-1 , … , 2 .

Pasul 2. [Gasiti max(K1 , … , Kj).] Se compara cheile Kj , Kj-1 , … , K1 pentru a se gasi

cea mai mare dintre ele ; fie aceasta Ki .

Pasul 3. [Interchimbati cu Rj .] Interschimbati inregistrarile Ri ↔ Rj (acum inregistrarile

Rj , … ,RN sunt in pozitia finala ) .

Exemplu :

Program de sortare prin selectie

#include <conio.h>

#include <stdlib.h>

#include <stdio.h>

int n;

typedef arr[100] sir;

sir x;

int i,j,n,l;

int min;

void selectie(sir x, int n)

{

for (int i=1; i < n-1; i++)

{

l=i;

min=x[i];

for (int j=i+1; j < n; j++)

{

if (min > x[j])

{

min=x[j];

l=j;

}

}

x[l]=x[i];

x[i]=min;

}

}

void citire(sir x, int n)

{

printf(“ Introduceti elementele vectorului:”);

for (int i=1; i < n ; i++)

scanf (“%d”,&x[i]);

}

void afisare(sir x, int n)

{

printf(“ Vectorul sortat:”);

for (int i=1; i < n ; i ++)

printf(“%d”,x[i]);

}

void main (void)

{

printf(“ Introduceti dimensiunea vectorului:”);

scanf(”%d”,&n);

citire(x,n);

selectie(x,n);

afisare(x,n);

}

Rafinamente ale sortarii prin selectie

Lema .

Orice algoritm pentru gasirea maximului din n elemente , bazat pe compararea perechilor de elemente , trebuie sa faca cel putin n-1 comparatii .

Demonstratie .

Daca se fac mai putin de n-1 comparatii , vor rezulta cel putin doua elemente care nu vor fi gasite niciodata ca fiind mai mici decat oricare altele . De aceea , nu vom sti nicio-data care din aceste doua elemente este mai mare si nu putem determina maximul .

Astfel un proces de selctie care afla elementul cel mai mare , trebuie sa aiba cel putin n-1 pasi .

Consideram cele 16 numere din tabelul prezentat anterior . Pentru a economisi timp , in selectia repetata se privesc aceste numere sub forma a patru grupe a cate patru elemente .

Se poate incepe determinarea elementului cel mai mare din fiecare grupa , si anume prin cheile respective , 512 , 908 , 653 , 765;

cel mai mare dintre aceste patru elemente , 908 , este cel mai mare din intregul fisier .

Pentru a obtine numarul secund cel mai mare e nevie sa comparam cele trei elemente din grupa care-l contine pe 908 ; cel mai mare din{170 , 897 , 275 ,} este 897 si cel mai mare din {512 , 897 , 653, 765} este 897 .

Similar pentru a obtine al treilea element cu valoarea cea mai mare se determina cel maimare dintre {170 , 275} si apoi cel mai mare din {512 , 275 , 653 , 765} si asa mai departe .

Fiecare noua selectie dupa cea dintai are cel mult 6 comparatii suplimentare. In general daca N este un patrat perfect , pentru impartirea fisierului in √ N grupe de √ N elemente fiecare , fiecare noua selectie , dupa prima are cel mult √ N – 1 comparatii in grupa elementului selectat anterior , plus √ N – 1 comparatii in "grupa liderilor". Aceasta se numeste slectie patratica ; timpul total de executie este O(N√ N ) , care este mult mai bun decat N2 .

Selectia patratica a fost publicata pentru prima data de E.H. Friend in 1956 .

4.2. SORTARE DE ANSAMBLE

Se spune ca un fisier de chei K1 , K2 , … , KN reprezinta un "ansamblu" daca :

K[j/2] ≥ Kj pentru 1 ≤ [j/2] < j ≤ N

Astfel : K1 ≥ K2 , K1 ≥ K3 , K1 ≥ K4 etc. ; aceasta este exact conditia care implica , in particular ca cheia cea mai mare apare in "varful ansamblului" , K1 = max(K1 , K2 , … , KN) .

O metoda eficienta pentru crearea ansamblului a fost sugerata de R.W.Floyd in 1964.

Sa presupunem ca suntem capabili sa aranjam un fisier astfel incat

K[j/2] ≥ Kj pentru l < [j/2] < j ≤ N ,

unde l este un numar oarecare ≥ 1. (In fisierul original , aceasta conditie se mentine

"vida " pentru l = [N/2] , deoarece nici un indice nu satisface conditia [N/2] < [j/2] < j ≤ N) . Nu este dificil de vazut cum se transforma fisierul , astfel uncat inegalitatile de mai sus sa fie extinse la cazul [j/2] = l , lucrand in totalitate in subarborele a carui radacina este nodul l. Aceste idei au condus la urmatorul algoritm :

Algoritm de sortare de ansamble

Sunt de aranjat inregistrarile R1 , R2 , … , RN ; dupa ce sortarea este completa , cheile vor fi in ordine , K1 , K2 , … , KN . La inceput rearanjam fisierul , astfel incat sa formeze un ansamblu , apoi repetam inlocuirea varfului ansamblului si il transferam in pozitia lui finala . Presupunem ca N ≥ 2.

Pasul 1. [Initializare.] Punem l = [N/2] + 1 , r← N .

Pasul 2. [Descreste l sau r.] Dac l > 1, punem l ← l – 1 , R ← R 1 , K ← Kl . (Daca l > 1,

suntem in procesul de transformare a fisierului de intrare intr-un ansamblu ; pe

de alta parte , daca l = 1 , cheile K1 , K2 , … , Kr constituie inca un ansamblu.)

Altfel punem R ← Rr , K ← Kr , Rr ← R1 si r ← r-1 ; daca aceasta face r = 1 ,

punem R1← R si terminam algoritmul .

Pasul 3. [Prepara pentru "cernere".] Punem j ← l . (In acest punct avem K[j/2] ≥ Kj pentru

l < [j/2] < j ≤ N ; si inregistrarile R sunt in pozitii finale pentru r ≤ k ≤ N . Pasii

3 , 4 , … , 8 reprezinta algoritmul de "cernere" ; efectul lor este echivalent cu

punerea lui Rl ← R si apoi rearanjand Rl …Rr , astfel incat conditia K[j/2] ≥ Kj

pentru l < [j/2] < j ≤ N sa se mentina de asemenea , pentru [j/2] = l ).

Pasul 4. [Mergi in jos.] Pune i ← jsi j ← 2j . (In pasii urmatori avem i = [j/2] . Daca j < r

se trece direct la pasul 5 ; daca j = r se trece la pasul 6 ; si dac j > r , se trece la

pasul 8 .)

Pasul 5. [Gaseste fiul "cel mai mare".] Daca Kj < Kj+1 , atunci punem j ← j+1 .

Pasul 6. [Este mai mare decat K ?] Daca K ≥ Kj , atunci trecem la pasul 8 .

Pasul 7. [Deplaseaza-l in sus .] Punem Ri ← Rj , si ne intoarcem la pasul 4 .

Pasul 8. [Memoreaza R.] Punem Ri ← R . (Aceasta termina algoritmul de "cernere "

initiat in pasul 3). Ne reintoarcem la pasul 2 .

CAPITOLUL 5

SORTARE PRIN INTERCLASARE

SORTARE PRIN INTERCLASARE CU DOUA CAI

SORTARE PRIN INTERCLASARE DE LISTE

SORTARE PRIN INTERCLASARE

Interclasarea inseamna combinarea a doua sau mai multor fisiere , ordonate intr-un singur fisier ordonat . De exemplu putem interclasa doua fisiere 503 , 703 , 765 si 087 , 512, 677 pentru a obtine 087 503 512 677 703 765 .Un mod simplu pentru relizare acestui lucru este de a compara elementele cele mai mici , de a extrage pe cel mai mic si apoi de a se repeta acelasi procedeu mai departe . Incepand cu

503 703 765

087 512 677

obtinem 087 503 703 765

,

512 677

apoi 087 503 703 765

,

512 677

si asa mai departe . Cand unul din cele doua fisiere este epuizat este necesara ceva mai multa atentie .

5.1. Algoritmul de sortare prin interclasare cu doua cai

Acest algoritm interclaseaza fisierele ordonate x1 ≤ x2 ≤ …≤ xm si y1 ≤ y2 ≤… ≤yn intr-un singur fisier z1≤ z2≤…≤zn+m .

Pasul 1. [Initializare .] Stabileste i← 1, j← 1, k← 1 .

Pasul 2. [Gaseste pe cel mai mic .] Daca xi ≤ yj treci la pasul 3 , altfel treci la pasul 5 .

Pasul 3. [Extrage xi .] Stabileste zk← xi , k← k+1 , i← i+1 . Daca i ≤ m intoarce-te la

pasul 2 .

Pasul 4. [Transmite y1 ,…, yn .] Stabileste (zk , … , zm+n)← (yj , … , yn) si termina

algoritmul .

Pasul 5. [Extrage yj .] Stabileste zk← yj , k← k+1 , j← j+1 .Daca j ≤ n intoarce-te la

pasul 2.

Pasul 6. [Transmite xi , … , xm .] Stabileste (zk ,…, zm+n)← (xi , … , xm) si termina

algoritmul.

Program de sortare prin interclasare

#include <conio.h>

#include <stdlib.h>

#include <stdio.h>

int n;

typedef arr[100] vector;

void citire(var x:vector;n:integer)

{

int i;

for (int i=1; i<n; i++)

{

printf(“x[%d]=”,i);

scanf (“%d”,&x[i]);

}

}

void afisare(vector x; int n)

{

int n;

for (int i=1;i<n;i++)

printf(“%d”,x[i]);

}

void interclasare(int inf, int med, int sup)

{

int i,j,k,l;

vector y;

i=inf;

j=med+1;

k=inf;

while (i<=med) and (j<=sup)

{

if (x[i]<=x[j])

{

y[k]=x[i];

i=i+1;

}

else

{

y[k]=x[j];

j=j+1;

}

k=k+1;

}

for (int l=i; l < med; l++)

{

y[k]=x[l];

k=k+1;

}

for (int l=j; l < sup; l++)

{

y[k]=x[l];

k=k+1;

}

for (int l=inf; l < sup; l++)

x[l]=y[l];

}

void sortare(int inf, int sup)

{

int med;

if (inf<sup)

{

med=(inf+sup) / 2;

sortare(inf,med);

sortare(med+1,sup);

interclasare(inf,med,sup);

}

}

void main ()

{

printf(“ Dimensiunea vectorului:“);

scanf(“%d”,&n);

citire(x,n);

printf(“\n Vectorul inainte de sortare: “);

afisare(x,n);

sortare(1,n);

printf(“ Vectorul sortat: “);

afisare(x,n);

getch() ;

}

5.2. Algoritm de sortare prin interclasare naturala folosind doua cai

Inregistrarile R1 , … , RN sunt sortate utilizand doua arii din memorie , fiecare din ele fiind capabila sa detina N inregistrari . Pentru convenienta vom spune ca inregistrarile din a doua arie sunt RN+1 , … , R2N iar continutul initial al acestei arii este imaterial . Dupa ce sortarea este completa cheile vor fi ordonate astfel K1≤ ….. ≤ KN .

Pasul 1. [Initializarea .] Stabileste s ← 0 .(Cand s = 0 vom transfera inregistrarile din (R1

….RN) in aria (RN+1 …. R2N) ; cand s = 1 , se va merge pe alta cale .)

Pasul 2. [Preparare pentru trecere.] Daca s = 0 , stabileste i ← 1, j← N , k ← N + 1 ,

l←2N ; daca s = 1 stabileste i← N + 1, j ← 2N , k ← 1 , l ← N . (Variabilele i ,

j , k , l indica pozitiile curente in fisierul sursa de citit si fisierul destinatie de

scris ). Stabileste d ← 1, f ← 1 . (Varibila d da directia curenta a iesirii ; f este

stabilit la 0 daca sunt necesare viitoare treceri).

Pasul 3. [Compara Ki : Kj .] Daca Ki > Kj treci la pasul 8 . Daca i = j , stabileste Rk ← Ri

si treci la pasul 13 .

Pasul 4. [Transmite Ri .] Stabileste Rk ← Ri , k ← k+d .

Pasul 5. [Pas in jos ?] Creste i cu 1 . Apoi daca K i-1 ≤ Ki intoarcete la pasul 3 .

Pasul 6. [Transmite Rj .] Stabileste Rk ← Rj , k ← k+d .

Pasul 7. [Pas in jos ?] Descreste j cu 1 . Apoi , daca Kj+1 ≤ Kj intoarce-te la pasul 6 ;

altfel treci la pasul 12.

Pasul 8. [Transmite Rj .] Stabileste Rk ← Rj , k ← k+d .

Pasul 9. [Pas in jos ?] Descreste j cu 1 . Apoi daca , Kj+1 ≤ Kj intoarce-te la pasul 3 .

Pasul 10. [Transmite Ri .] Stabileste Rk ← Ri , k ← k+d .

Pasul 11. [Pas in jos ?] Creste i cu 1 . Apoi daca K i-1 ≤ Ki intoarcete la pasul 10.

Pasul 12. [Schimba partile .] Stabileste f ← 0 , d ← – d si interschimba k ↔ l . intoarce-

te la pasul 3 .

Pasul 13. [Schimba aria .] Daca f = 0 , stabileste s ← 1-s si intoarce-te la pasul 2 . Altfel ,

sortarea este completa ; daca s = 0 , stabileste (R1 ….RN) ← (RN+1 …. R2N) .

Exemplu :

Tabelul prezinta sortarea prin interclasare intr-o maniera similara cu procedura de descompunere utilizata in sortarea rapida , a sortarii dupa ranguri cu interschimb , etc .

Examinam intrarea de la dreapta si de la stanga catre mijloc . Ignorand linia din varful tabelului pe moment sa consideram transformarea liniei 2 in 3 . La stanga avem sirul ascendent 503 703 765 ; la dreapta citind spre stanga se intalnesc datele 087 512 677. Interclasarea acestor doua secvente conduce la 087 503 512 677 703 765 , care este plasat la stanga liniei 3 . Apoi cheile 061 612 908 in linia 2 sunt interclasate cu 170 509 897 si rezultatul 061 170 509 612 897 908 este plasat la sfarsitul liniei 3 , in dreapta .

In sfarsit , 154 275 426 653 este interclasat cu 653 si rezultatul este plasat la stanga . linia a doua din tabel a fost formata in acelasi mod , din intrarea initiala in linia 1.

Liniile verticale din tabel reprezinta limitele intre citiri .Acestea sunt asa numitii "pasi in jos" unde un element mai mic urmeaza dupa un element mai mare .

5.3. Algoritm de sortare prin interclasare directa cu doua cai

Inregistrarile R , … , R sunt sortate utilizand doua arii de memeorie , ca in algorimul anterior .

Pasul 1. [Initializeaza .] Stabileste s← 0 , p← 1 .(Semnificatia variabilelor s,i,j,k,l,d este

aceeasi ca si in algoritmul precedent .Aici p reprezinta marimea monotoniilor

crescatoare de interclasare in trcerea curenta ; q si r pastreaza evidenta numerelor

elementelor neinterclasate dintr-o momotonie .)

Pasul 2 . [Prepara trecerea .] Daca s=0 , stabileste i← N , k← N , l← 2N+1 ; daca s=1 ,

stabileste I← N+1 , j← 2N , k← 0 , l← N+1 . Apoi stabileste d← 1 , q← p ,

r← p .

Pasul 3 .[Compara Ki : Kj .] Daca Ki > Kj treci la pasul 8 .

Pasul 4 .[Transmite Ri .] Stabileste k← k+d , Rk← Ri .

Pasul 5. [Sfarsitul sirului ?] Stabileste i← i+1 , q← q-1 . Daca q>0 intoarece-te la pasul

3.

Pasul 6 . [Transmite Rj .] Stabileste k← k+d .Apoi , daca k=l , treci la pasul 13 ; altfel

stabileste Rk← Rj .

Pasul 7 . [Sfarsitul sirului ?] .] Stabileste j← j-1 , r← r-1 .Daca r>0 , treci la pasul 6 ;

altfel treci la pasul 12 .

Pasul 8 .[Transmite Rj .] Stabileste k← k+d , Rk← Rj .

Pasul 9. [Sfarsitul sirului ?] Stabileste j← j-1 , r← r-1 .Daca r>0 , treci inapoi la pasul 3.

Pasul 10. [Transmite Ri .] Stabileste k← k+d .Apoi , daca k=l , treci la pasul 13 ; altfel

stabileste Rk← Ri .

Pasul 11. [Sfarsitul sirului ?] Stabileste i← i+1 , q← q-1 . Daca q>0 intoarece-te la

pasul 10.

Pasul 12. [Comuta partile .] Stabileste q← p , r← p , d← -d , si interschimba k↔ l .

Intoarece-te la pasul 2. Daca nu , sortarea este completa ; s=0 , stabileste

(R1 , …, RN)←(RN+1 ,…, R2N).

Pasul 13. [Comuta partile .] Stabileste p← p+p . Daca p< N , stabileste s← 1-s si

intoarce-te la pasul 2 .Daca nu , sortarea este completa ; daca s=0 , stabileste

(R1 , …, RN)←(RN+1 ,…, R2N).

Exemplu :

5.4. Algoritmul de sortare prin interclasare de liste

Se presupune ca inregistrarile R1 ,…, RN contine K1 , …, KN chei si L1, …, LN

" campuri de legatura "capabile sa detina numere de la N , pana la N+1 . Exista doua campuri auxiliare de legatura L0 si LN+1 , in inregistrarile artificiale R0 si RN+1 la inceputul si la sfarsitul fisierului .

Acest algoritm de sortare este o "sortare de liste ", care stabileste campurile de legatura astfel incat inregistrarile sunt legate impreuna , in ordine ascendenta .Dupa ce sortarea este completa , L0 este indexul inregistrarii cu cheia cea mai mica ; si pentru 1≤ k≤ N , L este indexul inregistrarii care urmeaza Rk sau Lk =0 , daca Rk este inregistrat cu cheia cea mai mare .

Pe parcursul acestui algoritm , R0 si RN+1 servesc drept "capete de liste " pentru doua liste lineare ale caror subliste sunt de interclasat . O legatura negativa arata sfarsitul unei subliste cunoscute spre a fi ordonata ; legatura zero arata sfarsitul intregii liste .

Presupunem ca N≥ 2. Notatia "│L│← p " are semnificatia " stabileste Ls pentru p sau -p retinand semnul anterior a lui Ls ".

Pasul 1. [Prepara doua liste] Stabileste L0←1 , LN+1← 2, Li← -(i+2) pentru

1≤ i≤ N-2 si LN-1← LN← 0 .(S-au creat astfel doua liste continand

respectiv R1 ,R3, R5, …si R2, R4, R6 …;) legaturile negative indica faptul ca

fiecare "sublista " ordonata contine numai un element .

Pasul 2. [Incepe un nou pas .] Stabileste s← 0, t← N+1 ,p← Ls , q ←Lt .Daca q=0

algoritmul s-a terminat .(Pe parcursul fiecarui pas , p si q traverseaza listele

care se interclaseaza ; s de obicei indica inregistrarea cea mai recent

prelucrata din sublista curanta in timp ce t- indica sfarsitul listei iesita

anterior.)

Pasul 3.[Compara Kp: Kq .] Daca Kp >Kq , treci la pasul 6.

Pasul 4.[Avanseaza p.] Stabileste │ Ls│← p, s← p , p← Lp .Daca p>0 , intoarce-te

la pasul 3.

Pasul 5.[Termina sublista .] Stabileste Ls← q, s← t .Apoi stabileste t← q si q← Lq ,

odata sau de mai multe ori ,pana cand q≤ 0.In final treci la pasul 8.

Pasul 6.[Avanseaza q.] (Pasii 6 si 7 sunt 4 si 5 .) Stabileste │Ls │← q , s← q,q← Lq.

Daca q>0 intoarce-te la pasul 3 .

Pasul 7.[Termina sublista.] Stabileste Ls← p, s← t .Apoi stabileste t← p si p← Lp odata sau de mai multe ori pana p≤ 0 .

Pasul 8.[Sfarsitul trecerii ?] (La acest punct , p≤ 0si q≤ 0 , deoarece ambii indicatori

s-au miscat catre sfarsitul sublistelor lor corespunzatoare .)Stabileste p← -p

q ←-q.Daca q=0 , stabileste │Ls│← p , │Lt│←0 si intoarce-te la pasul 2.

Altfel intoarce-te la pasul 3.

Exemplu :

CAPITOLUL 6

SORTARE PRIN DISTRIBUTIE

6.1. Algoritm de sortare dupa ranguri a listelor

Se presupune ca inregistrarile R1 , …, RN contin fiecare un camp de legatura LINK .

Cheile lor se presupune ca sunt p-tuplii

(ap, …,a2 a1) , 0 ≤ ai ≤ M ,

unde ordinea este definita lexicografic , astfel ca

(ap,…,a2 a1) < (bp ,…,b2 b1)

daca si numai daca pentru un j oarecare , 1≤ j ≤ p avem :

ai=bi pentru toti i > j , dar aj < bj .

Cheile pot fi gandite in particular ca numere scrise in notatia in baza M.

ap Mp-1 + … + a2 M +a1 ,

si in acest caz ordinea lexicografica corespunde ordonarii normale a numerelor nenegative.Cheile pot fi de asemenea insirate dupa ordinea literelor din alfabet.

Sortarea se face prin pastrarea a M "gramezi " de inregistrari .Exista doi indicatori de variabile TOP[i] si BOTM[i] pentru fiecare gramada , 0≤ i < M si presupunem ca

LINK (LOC(BOTM([i]))) = BOTM[i] .

Pasul 1.[Cicleaza pe k .] La inceput , stabileste P← LOC(RN ), un indicator pentru ultima

inregistrare . Apoi realizeaza pasii 2 pana la 6 pentru k= 1,2, …,p.(Pasii 2 pana la

6 constituie o "trecere".) Apoi algoritmul se termina cu P indicand inregistrarea

cu cheia cea mai mica , LINK (P) inregistrarea cu urmatoarea cheie cea mai mica,

apoi LINK(LINK(P)) ; LINK in inregistrarea finala va fi Λ .

Pasul 2. [Stabileste gramezile vide .] Stabileste TOP[i]←LOC(BOTM[i]) si

BOTM[i]←Λ , pentru 0 ≤ i < M .

Pasul 3. [Extrage a k-lea rang din cheie.] Fie KEY(P) , cheia in inregistrare chemata prin

P, de forma (ap, …,a2 a1) ; stabileste i ← ak , al k – lea rang mai putin

semnificativ din aceasta cheie .

Pasul 4. [Ajusteaza legatura .] Stabileste LINK (TOP[i])← P , apoi stabileste TOP[i] ←P

Pasul 5.[Pas spre urmatoarea inregistrare .] Daca k = 1 (primul pas) si daca P = LOC(Rj)

pentru j oarecare j ≠ 1 , stabileste P← LOC(Rj-1) si intoarce-te la pasul 3 . Daca

k>1 (pasul urmator) stabileste P← LINK(P) , si intoarce-te la pasul 3 daca P ≠ Λ.

Pasul 6. [Executa algoritmul de asamblare a sirurilor.] (Toate elementele sunt acum

distribuite in gramezi .) Algoritmul de asamblare a sirurilor "prinde impreuna "

gramezile individuale intr-o lista pregatindu-le pentru pasul urmator . Apoi

stabileste P←BOTM[0] , care formeaza primul punct al elementului din lista

grupata.

6.2. Algoritmul de asamblare a sirurilor

Dandu-se M siruri inlantuite in conformitate cu algoritmul de sortare dupa ranguri a listelor , acest algoritm ajusteaza cel mult M legaturi astfel incat creeaza un singur sir , cu BOTM[0] indicand primul element , gramada 0 fiind urmata de gramada 1 , … , urmata de gramada (M-1)

Pasul 1. [Initializare.] Stabileste i ← 0 .

Pasul 2. [Indica varful gramezii.] Stabileste P← TOP[i] .

Pasul 3. [Urmatoarea gramada.] Creste cu I cu 1 . Daca I=M , stabileste LINK(P)←Λ

si termina algoritmul .

Pasul 4. [Gramada este vida ?] Daca BOTM [i] = Λ , intoarce-te la pasul 3.

Pasul 5. [Leaga gramezile impreuna .] Stabileste LINK(P)← BOTM[i] .Intoarce-te

la pasul 2 .