Sortarea vectorilor
In urmatorul articol voi prezenta cateva dintre metodele clasice de sortare a unui vector,in ordinea
inversa a eficientei lor,criteriile de departajare fiind explicate pe larg mai [Link] va cuprinde:
0. [Link] sortarii unui vector
1. Criterii de departajare
2. Bubble Sort [ interschimbare]
3. Selection Sort [ selectie ]
4. Insertion Sort [ inserare]
5. Shell sort [insereare]
6. Merge sort [ interclasare ]
7. Heapsort [ selectie]
8. LSD Radix sort [ procesare individuala a cifrelor]
9. Quicksort [partitionare]
10. Introsort [hibrid]
11. Implementari cu ajutorul STL
0. [Link] sortarii unui vector
Prin sortare intelegem algoritmul prin care putem rearanja k elemente intr-o anumita ordine (de
exemplu: in ordine lexicografica, ordine crescatoare).
Sortarea este des folosita in lucrul cu liste. Un exemplu de folosire a sortarii il reprezinta motoarele
de cautare web, care folosesc astfel de algoritmi (Google, Yahoo, MSN).
1. Criterii de departajare
Pentru a putea departaja cat mai bine si a pune la dispozitie o gama cat mai larga de tehnici de
sortare ,algoritmii de mai jos vor fi comparati in functie de cazul mediu,cazul cel mai
nefavorabil,memorie folosita cat si de stabilitate.
2. Bubble Sort
A. Cazul mediu : O(N^2)
B. Cazul cel mai nefavorabil : O(N^2)
C. Memorie folosita : O(1)
D. Stabil : DA
E.0. Sortare descrescatoare : a[ i ] < a[ i+1 ]
E.1. Sortare crescatoare : a [ i ] > a[ i+1 ]
Descriere :
Sortarea prin metoda bulelor se considera drept una din cele mai putin efective metode de sortare
dar cu un algoritm mai putin complicat.
Ideea de baza a sortarii prin metoda bulelor este in a parcurge tabloul de la stanga spre dreapta, fiind
comparate elementele alaturate a[ i ] si a[i+1]. Daca vor fi gasite 2 elemente neordonate valorile lor
vor fi interschimbate.
Parcurgerea tabloului de la stinga spre dreapta se va repeta atat timp cat nu vor fi intalnite elemente
neordonate.
Implementare :
Code:
void bubble(int a[],int n)
{
int i,schimbat,aux;
do
{
schimbat = 0;
for(i = 0; i < n-1; i++) //parcurgem vectorul
if(a[i] < a[i+1]) //daca valoarea i din vectorul a
este mai mica decat cea de pe pozitia i+1
{ //interschimbare
aux = a[i];
a[i] = a[i+1];
a[i+1] = aux;
schimbat = 1;
}
}while(schimbat);
}
3. Selective Sort
A. Cazul mediu : O(N^2)
B. Cazul cel mai nefavorabil : O(N^2)
C. Memorie folosita : O(1)
D. Stabil : DA
E.0. Sortare descrescatoare : min < a[j]
E.1. Sortare crescatoare : min > a[j]
Descriere :
Acest algoritm selecteaza la fiecare pas`ul i cel mai mic element din vectorul de la pasul i+1 pana la
[Link] minima de la pasul i este pusa in vector la pozitia i,facandu`se intereschimbarea cu pozitia
actuala a [Link] este un algoritm indicat pentru vectorii mari,in majoritatea cazurilor oferind
rezultate mai slabe decat insertion sort.
Implementare :
Code:
void selective(int a[],int n)
{
int i,aux,min,minat;
for(i = 0; i < n - 1;i++)
{
minat = i;
min = a[i];
for(j = i + 1;j < n;j++) //selectam minimul din vectorul ramas( de
la i+1 la n)
{
if(min > a[j]) //sortare crescatoare
{
minat = j; //pozitia elementului minim
min = a[j];
}
}
aux = a[i] ;
a[i] = a[minat]; //interschimbare
a[minat] = aux;
}
}
4. Insertion Sort
A. Cazul mediu : O(N^2)
B. Cazul cel mai nefavorabil : O(N^2)
C. Memorie folosita : O(1)
D. Stabil : DA
E.0. Sortare descrescatoare : j > 0 && a[j - 1] < a[j]
E.1. Sortare crescatoare : j > 0 && a[j - 1] > a[j]
Descriere :
Spre deosebire de alti algoritmi de sortare, sortarea prin insertie este folosita destul de des pentru
sortarea tablourilor cu numar mic de elemente. De exemplu, poate fi folosit pentru a imbunatati
rutina de sortare rapida.
Sortarea prin insertie seamana oarecum cu sortarea prin selectie. Tabloul este impartit imaginar in
doua parti - o parte sortata si o parte nesortata. La inceput, partea sortata contine primul element al
tabloului si partea nesortata contine restul tabloului. La fiecare pas, algoritmul ia primul element din
partea nesortata si il insereaza in locul potrivit al partii sortate. Cand partea nesortata nu mai are nici
un element, algoritmul se opreste.[/i].
Implementare :
Code:
void insertion(int a[], int n)
{
int i, j, aux;
for (i = 1; i < n; i++)
{
j = i;
while (j > 0 && a[j - 1] > a[j])
{
aux = a[j];
a[j] = a[j - 1];
a[j - 1] = aux;
j--;
}
}
}
5. Shell Sort
A. Cazul mediu : -
B. Cazul cel mai nefavorabil : O(N * log^2 N)
C. Memorie folosita : O(1)
D. Stabil : NU
E.0. Sortare descrescatoare : j >= h && a[j-h] < v
E.1. Sortare crescatoare : j >= h && a[j-h] > v
Descriere :
Algoritmul shell sort este o generalizare a algoritmului insertion sort. La algoritmul insertion sort,
pentru a insera un nou element în lista de elemente deja sortate, se deplasează fiecare element cu
câte o poziţie spre dreapta atât timp cât avem elemente mai mari decât el. Practic fiecare element
înaintează spre poziţia sa finală cu câte o poziţie.
Algoritmul shell sort lucrează similar, doar că deplasează elementele spre poziţia finală cu mai mult
de o poziţie. Se lucrează în iteraţii. În prima iteraţie se aplică un insertion sort cu salt s1 mai mare
decât 1. Asta înseamnă că fiecare element din şirul iniţial este deplasat spre stânga cu câte s1 poziţii
atât timp cât întâlneşte elemente mai mari decât el.
Se repetă asemenea iteraţii cu salturi din ce în ce mai mici s2, s3, s4, etc. Ultima iteraţie se face cu
saltul 1. Această ultimă iteraţie este practic un insetion sort clasic.
Principiul este că după fiecare iteraţie şirul devine din ce în ce “mai sortat”. Iar cum algoritmul
insertion sort funcţionează cu atât mai repede cu cât şirul este mai sortat, per ansamblu vom obţine
o îmbunătăţire de viteză.
Implementare :
Code:
void shell(long a[],long n)
{
long i, j, k, h, v;
long cols[] = {1391376, 463792, 198768, 86961, 33936, 13776, 4592,
1968, 861, 336, 112, 48, 21, 7, 3, 1};
for (k = 0; k < 16; k++) //parcurgem fiecare limita
{
h = cols[k];
for (i = h; i < n; i++)//insertion sort
{
v = a[i];
j = i;
while (j >= h && a[j-h] > v) //crescator
{
a[j] = a[j-h];
j = j - h;
}
a[j] = v;
}
}
}
6. Merge Sort
A. Cazul mediu : O(N log N)
B. Cazul cel mai nefavorabil : O(N log N)
C. Memorie folosita : O(N)
D. Stabil : DA
E.0. Sortare descrescatoare : b[ i ] >= a[j]
E.1. Sortare crescatoare : b[ i ] <= a[j]
Descriere :
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.
Implementare :
Code:
void mergesort(int a[],int st, int m, int dr)
{
int b[100];
int i, j, k;
i = 0; j = st;
// copiem prima jumatate a vectorului a in b
while (j <= m)
b[i++] = a[j++];
i = 0; k = st;
// copiem inapoi cel mai mare element la fiecare pas
while (k < j && j <= dr)
if (b[i] <= a[j]) //crescator
a[k++] = b[i++];
else
a[k++] = a[j++];
// copiem elementele ramase daca mai exista
while (k < j)
a[k++] = b[i++];
}
void merge(int a[],int st, int dr)
{
if (st < dr)
{
int m = (st+dr)/2;
merge(a,st, m);
merge(a,m+1, dr);
mergesort(a,st, m, dr);
}
}
7. Heap Sort
A. Cazul mediu : O(N log N)
B. Cazul cel mai nefavorabil : O(N log N)
C. Memorie folosita : O(1)
D. Stabil : NU
E.0. Sortare descrescatoare :
if (a[w+1]<a[w]) w++;
if (a[v]<=a[w]) return;
E.1. Sortare crescatoare :
if (a[w+1]>a[w]) w++;
if (a[v]>=a[w]) return;
Descriere :
Algoritmul HeapSort este cel mai slab algoritm de clasa O(N log2N)
Este mai slab (dar nu cu mult) decat algoritmii din familia QuickSort, dar are marele avantaj fata de
acestia ca nu este recursiv.
Algoritmii recursivi ruleaza rapid, dar consuma o mare cantitate de memorie, ceea ce nu le permite
sa sorteze tablouri de dimensiuni oricat de mari
HeapSort este un algoritm care "impaca" viteza cu consumul relativ mic de memorie.
Implementare
Code:
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);
}
}
8. LSD Radix Sort
A. Cazul mediu : O(N * (k/s))
B. Cazul cel mai nefavorabil : O(N * (k/s))
C. Memorie folosita : O(N)
D. Stabil : DA
Descriere :
LSD Radix Sort este una dintre cele mai rapide metode de [Link] se bazeaza pe sortarea in
functie de cea mai nesemnificativa cifra(least significant digit).Aceasta metoda de sortare este
avantajoasa datorita usurintei cu care poate fi folosita si la alte tipuri de date decat cele intregi.
Dezavantajul il reprezinta implementarea dificila,necesitand folosirea operatiilor pe biti,memoria
mare folosita,cat si problemele de sortare ce apar in cazul numerelor negative.
Implementare :
Code:
#define COUNT_N 256 //65536 pt long long
#define BYTE 8 // 16 pt long long
#define N_MAX 1000000
int a[N_MAX],b[N_MAX],count[COUNT_N],ind[COUNT_N];//long echivalent cu
int sub g++
void rad(int *a,int *b,int byte,int n)
{
memset(count,0,sizeof(count));
int i,Lm = COUNT_N - 1;
for(i = 0; i < n; ++i)
++count[(a[i]>>byte)&Lm];
for(i = 0;i < COUNT_N; ++i)
ind[i] = ind[i-1] + count[i-1];
for(i = 0; i < n; ++i)
b[ind[(a[i]>>byte)&Lm]++] = a[i];
}
void radix(int *a,int n)
{
rad(a,b, 0,n);
rad(b,a, BYTE,n);
rad(a,b,2*BYTE,n);
rad(b,a,3*BYTE,n);
}
9. Quick Sort
A. Cazul mediu : O(N log N)
B. Cazul cel mai nefavorabil : O(N^2)
C. Memorie folosita : O(log N)
D. Stabil : DA
E.0. Sortare descrescatoare : Inversarea semnelor de comparatie pe liniile ce au ca si comentariu
"crescator"
E.1. Sortare crescatoare : Implementarea de mai jos
Descriere :
Quick Sort este unul dintre cei mai rapizi si mai utilizati algoritmi de sortare pana in acest
moment,bazandu`se pe tehnica "divide et impera".Desi cazul cel mai nefavorabil este O(N^2) ,in
practica,QuickSort ofera rezultate mai bune decat restul algoritmilor de sortare din clasa "O(N log
N)".
Implementare :
Code:
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++; //crescator
while(vector[max] > mijl) max--; //crescator
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
}
10. Intro Sort
A. Cazul mediu : O(N log N)
B. Cazul cel mai nefavorabil : O(N log N)
C. Memorie folosita : O(log N)
D. Stabil : DA
Descriere :
Introsort sau introspective sort este una dintre cele mai bune metode de sortare a unui [Link] se
bazeaza pe doi algoritmi studiati precedent(quick sort si heap sort).Algoritmul incepe sa lucreze cu
QuickSort ,dar cand recursivitatea atinge o anumita adancime(bazata pe numarul elementelor ce
urmeaza sa fie sortate) algoritmul continua sortarea cu ajutorul metodei [Link]
adusa QuickSort`ului in aceasta situatie va fi alegerea pivotului pe baza "median of 3" valorilor :
st,dr,mijl.
10. Implementari cu ajutorul STL
In libraria standard a limbajului C este implementata o varianta naiva de Quicksort,iar STL-ul ofera
programatorilor C++ o implementare a algoritmului Introsort, cat si functiile make_heap si sort_heap,
pentru a putea implementa usor Heapsort.
A. Quick Sort
Code:
#include <stdlib.h>
#include <stdio.h>
#define MAX_N 10000
int n, v[MAX_N];
int cmp(const void* x,const void *y);
int main(int argc, char *argv[])
{
int i;
freopen("[Link]","r",stdin);
freopen("[Link]","w",stdout);
scanf("%d",&n);
for(i = 0; i < n; i++ )
scanf("%d",v+i);
qsort(v,n,sizeof(v[0]),cmp);
for(i = 0;i < n;i++)
printf("%d ",v[i]);
return 0;
}
int cmp(const void*x, const void *y )
{
return *(int*)x - *(int*)y;
}
B. Intro Sort
Code:
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
vector<int> v;
int main()
{
int i, x, n;
freopen("[Link]","r",stdin);
freopen("[Link]","w",stdout);
scanf("%d",&n);
for(i = 0; i < n; i++ )
{
scanf("%d",&x);
v.push_back(x);
}
sort([Link](),[Link]());
for(i = 0; i < n; i++)
printf("%d ",v[i]);
return 0;
}
C. Heap Sort
Code:
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
vector<int> v;
int main()
{
int i, x, n;
freopen("[Link]","r",stdin);
freopen("[Link]","w",stdout);
scanf("%d",&n);
for(i = 0; i < n; i++ )
{
scanf("%d",&x);
v.push_back(x);
}
make_heap([Link](),[Link]());
sort_heap([Link](),[Link]());
for(i = 0; i < n; i++)
printf("%d ",v[i]);
return 0;
}