Prof. Popescu Doru Anastasiu, Universitatea din Pitești Autor, Prof. de informatică, Pietriș Constantin Daniel, Școala Gimnazială „Constantin… [625671]

UNIVERSITATEA DIN PITEȘTI
DEPARTAMENTUL PENTRU PREGĂTIREA
PERSONALULUI DIDACTIC

LUCRARE METODICO -ȘTIINȚIFICĂ
PENTRU OBȚINEREA
GRADULUI DIDACTIC I

Coordonator,
Prof. Popescu Doru Anastasiu, Universitatea din Pitești

Autor,
Prof. de informatică, Pietriș Constantin Daniel,
Școala Gimnazială „Constantin Brâncoveanu”, Slatina

SLATINA, an școlar 2018 – 2019

Studiu comparativ al metodelor de
sortare ?

Coordonator,
Prof. Popescu Doru Anastasiu, Universitatea din Pitești

Autor,
Prof. de informatică, Pietriș Constantin Daniel,
Școala Gimnazială „Constantin Brâncoveanu”, Slatina

SLATINA, an școlar 2018 – 2019

CUPRINS

1. Introducere
Una dintre cele mai importante probleme de programare atât din punct de vedere teoretic cât
și practic este sortarea datelor, și anume rearanjarea obiectelor într -o ordine crescătoare sau
descrescătoare. Sortarea este o operație fundamentală de informatică (multe programe o folosesc
ca pas intermediar) și ca urmare, a fost dezvoltat un număr mare de algoritmi de sortare. Care
dintre algoritmii de sortare este cel mai bun pentru o aplicație dată depinde de numărul de
obiecte care trebuie sortate, de gradul în care aceste obiecte sunt deja sortate într -un anumit fel și
de tipul de mediu electronic care urmează să fie folosit
Sortarea este un algoritm, prin intermediul c ăruia se poate ordona o anumita clasa de obiecte
concrete sau abstracte, dupa unu l sau mai multe criterii impuse.
Ca exemple se pot da :
– sortarea crescă toare sau descrescătoare a unui vector de numere și căutarea unui
număr sau a mai multor numere în acest ș ir de numere
– sortarea unei liste de persoane in ordinea alfabetica a numelor si prenumelor
acestora și că utarea u nei persoane sau a mai multor persoane cu anumite caracteristici
precizate.
– ordonarea unei liste de persoane dupa importanta muncii lor si cautarea unor
persoane dupa criterii precizate.
– ordonarea unei liste de persoane dupa anumite c riterii preferentiale si cautarea in
aceasta lista.

Donald E. Knuth a dedica t un volum întreg sortă rii si căutării într -o mulț ime de obiecte
concrete sau abstracte, intitulat sugestiv "Sortare si căutare" și care face parte din seria "Arta
Programarii Calculatoarelor ". Domeniul sortării si căutării oferă un mijloc ideal pentru analiza
unor game largi de subiecte generale importante :
– cum se pot descoperii algoritmii buni
– cum se pot optimiza algoritmii si programele
– cum s e poate analiza matematic eficienta algoritmilor
– cum se poate al ege rational cel mai bun dintre algoritmii necesari rezolvarii unei
clase de probleme
– cum se pot aprecia niste algoritmi ca fiind cei mai buni posibili
Fiecare aspect important al programarii isi gaseste rezolvarea in contextul sortarii si cautar ii.

2. Sortare si algoritmi de sortare

2.1. Definirea problemei sortarii

Fiind date n înregistrări, să se aranjeze aceste înregistrări în funcție de valorea câ mpului
K, numit cheie de sortare, astfel incat intre oricare doua inregistrari vecine R i si R i+1 sa existe una
dintre relatiile urmatoare intre cheile de sortare : K i < K i+1 sau K i > K i+1.
Relatia de ordine < sau > trebuie sa satisfaca urmatoarele conditii :
a. Una si numai una din variantele : a<b, a=b, a>b este adevarata (legea trihotomiei).
b. Daca a<b si b<c, atunci a<c (legea tranzitivitatii).
Pentru simplificarea prezentarii problemelor de sortare se vor aplica principalii
algoritmi de sortare asupra unor vectori care contin cheile de sortare iar pentru ca implementarea
lor in C ++ sa fie cat mai fireasca se va considera ca primul element al oricarui vector ocupa
pozitia zero si are, in consecinta, indexul zero.
2.2. Algoritmi de sort are
In functie de obiectivele urmarite pe parcursul ordonarii elementelor unui vector exista mai multi
algoritmi de sortare.

2.2.1. Sortarea prin metoda bulelor
Algoritmul de sortare prin metoda bulelor , cunoscut in literartura de specialitate ca
algoritmul Bubble Sort, este un algoritm uș or de implementat, majoritatea elevilor folosindu -l cu
predilectie .
Robert Sedgewick propunea eliminarea acestui algoritm din toate carț ile de algoritmi, iar
Donald E. Knuth preciza că sortarea prin metoda bulelor pare să nu aibă nimic recomandabil, cu Algoritmi
de sortare

Algoritmi de
sortare prin
comparații

Algoritmi de
sortare prin
numărare

Algoritmi de
sortare utilizând
metoda Divide et
impera

Sortare prin
metoda bulelor

Sortare prin
inserț ie

Sortare prin
interclasare

Sortare prin
selecție

Sortare rapidă

Sortare prin selecție
directă

Sortare prin selecție
arborescentă

Sortare HEAP

Sortare prin inserție
directă

Sortare prin inserție
binară

Sortare prin
Metoda Shell

excepția numelui ce capteaza atenția și a unor parametri al că ror studiu conduce la probleme
teoretice interesante .
Algoritmul are la baza d efinitia unui vector ordonat : Un vector V este ordonat crescător
sau descrescă tor daca pentru orice i natural din intervalul [0,n-1]exista proprietatea Vi < Vi+1,
respectiv Vi > Vi+1.

Raționamentul metodei:
Se repetă parcurgerea vectorului cu interschimbarea elementelor care nu respectă relația de ordine
cerută până când se ajunge la o parcurgere fără interschimbare.
Pentru a reține dacă a avut loc vreo interschimbare în timpul unei parcu rgeri algoritmul va folosi
o variabil ă de memorie schimb ce va putea avea una din dou[ valori posibile: 1 dacă a avut loc o
interschimbare sau 0 dacă nu a avut loc nicio interschimbare.
Reprezentarea algoritmului:
început bule
repetă
schimb ← 0
pentru i=0, n-2, execută
dacă V[i]>V[i+1] atunci
aux ← V[i ]
V[i] ←V[i +1]
V[i+1] ←aux
schimb ← 1
sfârșit dacă
sfârșit pentru
cât timp schimb=1
sfârșit bule
Pentru exemplificare vom urmari un tablou unidimensional V de 5 elemente ce va fi sortat crescător:
vectorul inițial

după prima parcurgere
13 7 17 11 23
7 13 11 17 23

după a doua parcurgere

vectorul final
Implementarea algoritmului în limbajul C++:
#include <iostream>
using namespace std;
int V[100],i,n,schimb,aux;
int main()
{
cout << "n=";
// citim num ărul de elemente ale vectorului
cin>>n;
//citim elementele vectorului
for(i=1; i<=n; i++)
cin>>V[i];
//sortam vectorul
do
{
schimb=0;
for(i= 0;i<n-1;i++)
if(V[i]>V[i+1])
{
aux=V[i];
V[i]=V[i+1];
V[i+1]=aux;
schimb=1;
} 7 11 13 17 23
7 11 13 17 23

}
while(schimb==1);
cout<<"Vectorul sortat crescator:"<<endl;
for(i= 0; i<n; i++)
cout<<V[i]<<" ";
return 0;
}
Sortarea prin metoda bulelor are complexitatea O(n2).

2.2.2 Sortarea prin selecție
Generalitati

2.2.2.1 Sortare prin selecție direct ă

Raționamentul metodei:
Se compară fiecare elemnt al vectorului cu fiecare dintre elementele ce -l urmează, selectându -se
astfel valoarea cea mai mica dintre elementele ramase nesortate ( în cazul sortării crescatoare).

Algoritmul:

început selecție directă
pentru i=1, n-1 executa
pentru j=i+1 , N executa
daca V[i]>V[j] atunci
interschimba V[i],V[j]
sfârșit daca
sfârșit pentru
sfârșit pentru
sfârșit selecție directă

Pentru exemplificare vom urmari un tablou unidimensional V de 5 elemente ce va fi sortat crescător:
vectorul inițial 13 7 17 11 23

după prima parcurgere

după a doua parcurgere

după a treia parcurgere

după a patra parcurgere

vectorul final

Implementarea algoritmului în limbajul C++:
#include <iostream>
using namespace std;
int V[100], i, j, n, aux;
int main()
{
cout << "n=";
// citim numărul de elemente ale vectorului
cin>>n;
//citim elementele vectorului
for(i=0; i<n; i++)
cin>>V[i];
//sortam vectorul
for(i= 0;i<n -1;i++)
for(j=i+1;j<n;j++)
if(V[i]>V[j])
{
aux=V[i];
V[i]=V[j];
V[j]=aux;
}
// afisare vector sortat
cout<<"Vectorul sortat crescator: "<<endl;
for(i=0; i<n; i++)
cout<<V[i]<<" ";
return 0;
} 7 13 17 11 23
7 11 17 13 23
7 11 13 17 23
7 11 13 17 23
7 11 13 17 23

2.2.2.2 Sortare prin selecție arborescenta
Descriere pseudocod cazpartic implementare
2.2.2.3 Sortare HEAP
Descriere pseudocod cazpartic implementare

2.2.3 Sortare prin inserție
Sortarea prin insertie se bazeaza pe aceleasi principii ca si cele aplicate de majoritatea
jucatorilor de carti, adica dupa ridicarea uncei carti de pe masa,aceasta se aseaza in pachetul din
mana la locul potrivit. Cu alte cuvinte,consideram ca avem vecto rul sortat a, iar la ivirea unui
nou element care se va adauga vectorului,el va fi pus pe locul potrivit printr -o insertie in
interiorul vectorului.

2.2.3.1 Sortare prin inserție directă

Raționamentul metodei:
Este cea mai simpla implementare a algoritmului si se face in felul urmator: Se considera ca
primele i elemente al vectorului sunt deja sortate.Pentru elementul al (i+1) -lea,din tabloul
initial,se va gasi pozitia in care trebuie inserat printre primele i elemente.Toate elementele
tabloului de la acasta pozitie si pana la i vor fi deplasate cu o pozitie mai la dreapta iar pozitia
eliberata va fi ocupata de elemntul i+1.

Algoritmul:
început inserție directă
pentru j= 0 ,n-2 executa
x=V[j]; i=j -1;
cât timp ((i>=0) && (x< V[i]))
V[i+1]= V[i]
i=i-1;
sf cat timp
V[i+1]=x
sf pentru

sfârșit inserție directă

Pentru exemplificare vom urmari un tablou unidimensional V de 5 elemente ce va fi sortat crescător:
vectorul inițial

după prima parcurgere

după a doua parcurgere

după a treia parcurgere

după a patra parcurgere

vectorul final

Implementarea algoritmului în limbajul C++:
#include <iostream>
using namespace std;
int V[100],i,j,n,x;
int main()
{
cout << "n=";
// citim numărul de elemente ale vectorului
cin>>n;
//citim elementele vectorului
for(i=0; i<n; i++)
cin>>V[i];
//sortam vectorul
for(j=0;j<=n -1;j++)
{
x=V[j]; i=j -1;
while ((i>=0) && (x<V[i]))
{
V[i+1]=V[i];
i=i-1;
}
V[i+1]=x; 13 7 17 11 23
13 7 17 11 23
7 11 17 13 23
7 11 13 17 23
7 11 13 17 23
7 11 13 17 23

}

// afisare vector sortat
cout<<"Vectorul sortat crescator:"<<endl;
for(i=0; i<n; i++)
cout<<V[i]<<" ";
return 0;
}

2.2.3.2 Sortare prin inserție binară
Descriere pseudocod cazpartic implementare
2.2.3.3 Metoda Shell
Descriere pseudocod cazpartic implementare

2.2.4 Algoritmi de sortare utilizând metoda Divide et impera
descriere
2.2.4.1 Sortare prin interclasare
Descriere pseudocod cazpartic implementare
2.2.4.2 Sortare rapidă
Descriere pseudocod cazpartic implementare

3. Aplicatii

4. Metodica

Raționamentul metodei:

Algoritmul:

Pentru exemplificare vom urmari un tablou unidimensional V de 5 elemente ce va fi sortat crescător:

Implementarea algoritmului în limbajul C++: