Metode de sortare
Ministerul Educației Naționale
Colegiul Național ”Petru Rareș”
Metode de sortare
Indrumador:
Prof. Marius Ududec
Absolvent,
Iascu Andrei
Introducere
Motivarea alegerii temei:
Am ales tema ”Metode de sortare” deoarece cunoașterea unor algoritmi de sortare este esențiala in programare, dar și in viața reală, fiind de mare ajutor in construirea și modificarea bazelor de date. De asemenea,este necesar și cunoașterea unor criterii de clasificare care indica metoda de sortare ideala pentru problema în cauză.
Descrierea Sortării
Se consideră un set finit de obiecte, fiecare având asociată o caracteristică, numită cheie, ce ia valori într-o mulțime pe care este definită o relație de ordine. Sortarea este procesul prin care elementele setului sunt rearanjate astfel încât cheile lor să se afle într-o anumită ordine.
Ex: Considerăm setul de valori întregi: (5,8,3,1,6). în acest caz cheia de sortare coincide cu valoarea elementului. Prin sortare crescătoare se obține setul (1,3,5,6,8) iar prin sortare descrescătoare se obține (8,6,5,3,1).
Sortarea este des folosită in lucrul cu liste. Un exemplu de folosire a sortării îl reprezintă motoarele de căutare web, care folosesc astfel de algoritmi (Google, Yahoo, MSN).
Metode de sortare
Stabilitate. O metodă de sortare este considerată stabilă dacă ordinea relativă a elementelor ce au aceeași valoare a cheii și nu se modifică în procesul de sortare.
Naturalețe. O metodă de sortare este considerată naturală dacă numărul de operații scade odată cu distanța dintre tabloul inițial și cel sortat. O măsură a acestei distanțe poate fi numărul de inversiuni al permutării corespunzătoare tabloului inițial.
Eficientă. O metodă este considerată eficientă dacă nu necesită un volum mare de resurse. Din punctul de vedere al spațiului de memorie o metodă de sortare pe loc este mai eficientă decât una bazată pe o zonă de manevră de dimensiunea tabloului. Din punct de vedere al timpului de execuție este important să fie efectuate cât mai puține operații. În general, în analiză se iau în considerare doar operațiile efectuate asupra elementelor tabloului (comparații și mutări). O metodă este considerată optimală dacă ordinul său de complexitate este cel mai mic din clasa de metode din care face parte.
Simplitate. O metodă este considerată simplă dacă este intuitivă si ușor de înțeles.
După cum bine știm, fiecare algoritm de sortare are nevoie de un anumit spațiu și un anumit timp pentru executarea algoritmului. Pentru măsurarea complexității vom folosi notația complexității „O(n)” (n reprezintă numărul de comparații ale algoritmului).
Cazul Mediu - situația in care probabilitatea duratei execuției algoritmului se apropie de media timpului de execuție al algoritmului respectiv.
Cazul defavorabil - situația in care timpul de execuție al algoritmului este cel mai ridicat.
Memorie folosită – memoria necesară sortării vectorului.
Tipuri de sortari
Bubble sort
Prin această metodă se parcurge vectorul şi se compară fiecare element cu succesorul său. Dacă cele două elemente nu sunt în ordine, ele se interschimbă. Vectorul se parcurge de mai multe ori, până când la o parcurgere completă nu se mai execută nicio interschimbare.
Se utilizează variabila sortat de tip int care se iniţializează cu valoarea 1 la începutul parcurgerii (se presupune că vectorul este sortat) şi, dacă în timpul parcurgerii se execută o interschimbare, variabilei sortat i se atribuie valoarea 0 (vectorul nu este sortat): Parcurgerea repetată a vectorului se termină atunci când, la sfârşitul unei parcurgeri, variabila sortat nu îşi modifică valoarea (îşi păstrează valoarea 1).
Algoritm
Subalgoritm Metoda_bulelor (A)
1: k=n {k va fi limita superioara pana unde se interschimba elemente}
2: repeta
3: ok = adevărat
4: pentru i=1,k-1 execută
5: dacă a[i] > a[i+1] atunci
6: ok = fals
7: aux = a[i]
8: a[i] = a[i+1]
9: a[i+1] = aux
10: j=i
11: k=j; {ultimul indice pentru care s-a facut interchimbare}
12: pana cand ok
Cazul mediu : O(N^2)
Cazul defavorabil : O(N^2)
Memorie folosita : O(1)
Stabil : DA
Algoritmul de sortare prin metoda selectiei directe
Prin această metodă se aduce pe prima poziţie elementul cu valoarea
cea mai mică din cele n elemente ale vectorului, apoi se aduce pe poziţia a doua
elementul cu cea mai mică valoare din ultimele n-1 elemente ale vectorului, apoi se
aduce pe a treia poziţie elementul cu cea mai mica valoare din ultimele n-2 elemente
ale vectorului ş.a.d.m.
#include <iostream>
using namespace.std;
int v[25],n,i,j,aux;
int main()
{
cout<<„nr de elemente=”;
cin>>n;
for(i=0;i<n;i++)
{
cout<<„v[„<<i<<„]=”;
cin>>v[i];}
for(i=0;i<n;i++)
cout<<v[i]<<” „;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if( v[i ]> v[j] )
{
aux=v[j]; v[j]=v[i]; v[i]=aux;
}
cout<<endl;
for(i=0;i<n;i++)
cout<<v[i]<<” „;
}
Merge sort - interclasare
In cazul sortarii prin interclasare vectorii care se interclaseaza sunt doua
secvente ordonate din acelasi vector.
Sortarea prin interclasare utilizeaza metoda Divide et Impera:
- se imparte vectorul in secvente din ce in ce mai mici., astfel incat fiecare secventa sa
fie ordonata la un moment dat si interclasata cu o alta secventa din vector
corespunzatoare.
- practic interclasarea va incepe cand se ajunge la o secventa formata din doua
elemente.
Aceasta odata ordonata se va interclasa cu o alta corespunzatoare. Cele doua
secvente vor alcatui in subsir ordonat din vector mai mare care la randul lui se va
interclasa cu subsirul corespunzator s.a.m.d.
Algoritm:
void mergesort(int left, int right) {
if (left == right)
return;
int middle = (left + right) / 2;
mergesort(left, middle);
mergesort(middle + 1, right);
//interclaseaza cele 2 siruri de la left la middle, si de la middle + 1 la right
.....
.....
}
Heap sort - selectie
Algoritmul HeapSort este cel mai slab algoritm de clasă O(N log2N) Este mai
slab (dar nu cu mult) decât algoritmii din familia QuickSort, dar are marele avantaj față
de aceștia că nu este recursiv. Algoritmii recursivi rulează rapid, dar consumă o mare
cantitate de memorie, ceea ce nu le permite să sorteze tablouri de dimensiuni oricât de mari HeapSort este un algoritm care "împăca" viteză cu consumul relativ mic de
memorie.
Cazul mediu : O(N log N)
Cazul defavorabil : O(N log N)
Memorie folosita : O(1)
Stabil : NU
Algoritm:
void swap(int a[],int i,int j)
{
int aux = a[i];
a[i] = a[j];
a[j] = aux;
}
void downheap(int a[],int v,int n)
{
int w = 2 * v + 1; // primul descendent al lui v
while (w<n)
{
if (w+1<n) // mai exista unul?
if (a[w+1]>a[w]) w++; //crescator
// w este decendentul lui v
if (a[v]>=a[w]) return; //crescator
swap(a,v, w); // interschimbam v cu w
v = w; // continuam
w = 2 * v + 1;
}
}
void heapsort(int a[],int n)
{
for (int v = n/2-1; v >= 0; v--) //creem heap`ul
downheap (a,v,n);
while (n>1)
{
n--;
swap(a,0, n);
downheap (a,0,n);
}
}
Quick sort - partionare
Quick Sorț este unul dintre cei mai rapizi și mai utilizați algoritmi de sortare până
în acest moment,bazându`se pe tehnică "divide et impera".Deși cazul cel mai
nefavorabil este O(N^2) ,în practică,QuickSort oferă rezultate mai bune decât restul
algoritmilor de sortare din clasă "O(N log N)".
Cazul mediu : O(N log N)
Cazul cel mai nefavorabil : O(N^2)
Memorie folosita : O(log N)
Algoritm:
void qSort(int vector[],int st,int dr)
{
int temp,min,max,mijl;
mijl = vector[st+(dr-st)/2]; //luam mijlocul intervalului
min = st; max = dr;
do
{
while(vector[min] < mijl) min++;
while(vector[max] > mijl) max--;
if(min <= max) //interschimbare
{
temp = vector[min];
vector[min++] = vector[max];
vector[max--] = temp;
}
}while(min <= max); //la fiecare pas sortam "mai bine" intervalul st-dr
//cand numai avem ce face schimbam intervalul
if(st < max) qSort(vector,st,max); //crescator
if(dr > min) qSort(vector,min,dr); //crescator
}