Metode de sortare a sirurilor

Metode de sortare a sirurilor

Se citesc n numere intregi. Se cere ca acestea sa fie scrise in ordine crescatoare/ descrescatoare . Exemplu: n=4 si se citesc numerele: 3,1,6,2. Numerele vor fi afisate in ordinea 1,2,3,6 (daca se cere sa fie scrise crescator) sau 6,3,2,1 (daca se cere sa fie scrise descrescator).

Operatia prin care se aranjeaza cele n numere in ordine crescatoare/ descrescatoare se numeste sortare.

Pentru a sorta cele n valori, acestea se citesc intr-o variabila de tip vector (sir). Sortarea propriu-zisa se face in cadrul acestei variabile.

1. Sortarea prin calculul minimului/maximului

Algoritmul este urmatorul:

• Se calculeaza minimul dintre valorile retinute, incepand cu prima pozitie;
• Minimul este trecut pe prima pozitie, prin interschimbarea continuturilor dintre componenta de indice 1 si componenta care il memoreaza.
• Se calculeaza minimul dintre valorile retinute, incepand cu a doua pozitie.
• Minimul este trecut pe a doua pozitie, prin interschimbarea continuturilor dintre componenta de indice 2 si componenta care il memoreaza.
• . . ..
• Se calculeaza minimul dintre valorile retinute, incepand cu penultima pozitie.
• Minimul este trecut pe penultima pozitie, prin interschimbarea continuturilor dintre componenta de indice n-1 si componenta care il memoreaza.

Exemplu: continutul variabilei care retine numerele citite este:

a
a[1] a[2] a[3] a[4]

Minimul este 1 si se gaseste pe pozitia 2. se inverseaza continuturile componentelor 1 si 2.

a
a[1] a[2] a[3] a[4]

Se calculeaza minimul dintre valorile retinute in componentele de la 2 la 4. Acesta este 2 si este retinut de componenta 4. Se inverseaza continutul componentelor 2 si 4.

a
a[1] a[2] a[3] a[4]

Se determina minimul dintre valorile retinute in componentele de la 3 la 4. Acesta este 3 si este retinut de componenta 4. Se inverseaza continutul componentelor 3 si 4.

a
a[1] a[2] a[3] a[4]

Acum, valorile se pot afisa. Procedeul a fost repetat de n-1 ori. In cazul in care se cere sortarea descrescatoare, la fiecare pas se calculeaza maximul (exercitiu!)

Algoritmul Sort_Min:

Date de intrare: a - sirul de valori care urmeaza sa fie sortate

n - numarul de valori din sirul a

Date de iesire: a - sirul sortat.

Algoritmul Sort_Min este urmatorul:

Citeste n;

Pentru i=1,n executa

Citeste a[i];

Sf_pentru;

Pentru i=1,n-1 executa

Min ← a[i]; k←i;

Pentru j=i+1,n executa

Daca a[j]<min atunci

min←a[j]; k←j;

sf_daca;

aux←a[k]; a[k] ←a[i]; a[i] ←aux;

sf_pentru;

sf_pentru;

pentru i=1,n executa scrie a[i];

sf_pentru

sf_Sort_Min.

2. Sortarea prin interschimbare

Algoritmul este urmatorul:

• Se parcurge sirul, inversand continuturile componentelor alaturate care nu sunt in ordine crescatoare (descrescatoare)
• . . ..
• Procedeul se repeat pana cand are loc o parcurgere in care nu se fac inversari.

Algoritmul Sort_Intersch:

Date de intrare: a - sirul care urmeaza sa fie sortat

n - numarul de elemente din sirul a

Date de iesire: a - sirul sortat crescator

Algoritmul Sort_Intersch este urmatorul:

Citeste n;

Pentru i=1,n executa citeste a[i];

Sf_pentru;

Repeta

Ok=fals;

Pentru i=1,n-1 executa

Daca a[i]>a[i+1] atunci

Ok ← adevarat;

aux←a[i]; a[i]←a[i+1]; a[i+1]←aux;

sf_daca;

sf_pentru;

Pana cand ok=fals;

Pentru i=1,n executa scrie a[i];

Sf_pentru;

Sf_Sort_Intersch.

Tema: Luati un exemplu concret, pe care sa testati algoritmul.

3. Sortarea prin insertie

Cu ajutorul variabilei citite a se aranjeaza valorile intr-o alta variabila, b, in ordine crescatoare. Pentru aceasta, se procedeaza astfel:

• b[1]=a[1];
• fiecare din valorile retinute de componentele de la 2 la n (in ordinea indicilor) se insereaza intre valorile ordonate deja ale sirului b.

Pentru realizarea inserarii unei valori, se parcurge sirul b de la dreapta la stanga pana cand se gaseste o componenta care retine o valoare mai mare decat cea care se insereaza, sau pana cand a fost parcurs intreg sirul. Incepand cu valoarea retinuta de componenta care va fi ocupata de valoarea inserata, toate valorile retinute se deplaseaza spre dreapta cu o pozitie.

Algoritmul Sort_Insertie:

Date de intrare: a - sirul care urmeaza sa fie sortat

n - numarul de elemente din sirul a

Date de iesire: b - sirul sortat crescator

Algoritmul Sort_Insertie este urmatorul:

Citeste n;

Pentru i=1,n executa citeste a[i];

Sf_pentru;

b[1] ← a[1];

pentru i=1,n executa

j←i-1;

cat timp (j>0)si(a[i]<b[j]) executa j←j-1;

sf_cattimp;

pentru k=i-1,j+1 executa b[k+1]←b[k];

sf_pentru;

b[j+1] ←a[i];

sf_pentru;

pentru i=1,n executa scrie b[i];

sf_pentru;

sf_Sort_Insertie

Tema: Luati un exemplu concret, pe care sa testati algoritmul.

4. Sortarea prin interclasare

Se citesc m numere intregi ordonate crescator (descrescator). De asemenea, se citesc alte n numere intregi ordonate crescator (descrescator). Se cere sa se afiseze toate numerele citite, in ordine crescatoare (descrescatoare).

Pentru rezolvarea problemei exista un algoritm classic, cel de interclasare, foarte performant. Presupunem ca sirurile de numere sortate se memoreaza in variabilele a si b. Numerele sortate vor fi memorate intr-un alt sir, numit c. La fiecare pas se alege un numar care va fi memorat in sirul c.

Algoritmul Sort_Intercl:

Date de intrare: a, b - sirurile cu elemente ordonate crescator

m - numarul de elemente din sirul a

n - numarul de elemente din sirul b

Date de iesire: c - noul sirul sortat crescator

k - numarul de elemente din sirul c.

Algoritmul Sort_Intercl este urmatorul:

Citeste m;

Pentru i=1,m executa citeste a[i];

Sf_pentru;

Citeste n;

Pentru i=1,n executa citeste b[i];

Sf_pentru;

i←1; j←1;k←1;

cat timp (i<=m)si(j<=n) executa

daca a[i]<b[j] atunci

c[k]:=a[i];

i←i+1;

altfel

c[k] ← b[j];

j←j+1;

sf_daca;

k←k+1;

sf_cattimp;

daca i<=m atunci

pentru j=i,m executa

c[k] ←a[j];

k←k+1;

sf_pentru

altfel

pentru i=j,n executa

c[k] ←b[i];

k←k+1;

sf_pentru;

sf_daca;

pentru i=1,k-1 executa scrie c[i];

sf_pentru;

sf_Sort_Intercl.