Sortarea

Metodele de sortare se clasifică în metode directe şi metode avansate. Metodele directe se bazează, pe algoritmi de dificultate redusă, uşor de găsit şi de înţeles. Metodele avansate se bazează pe algoritmi puţin mai complicaţi, dar care nu necesită cunoştinţe de algoritmică.

Metode directe

Această metodă se rezumă la a compara fiecare element cu celelalte, făcându-se interschimbarea dacă elemental mai mare are indexul mai mic. Este cea mai simplî metodă de sortare şi nu necesită cunoaşterea detaliată a limbajului de programare. Poate fi folosită cu success de începători. Bubble sort este o metodă de sortare simplă, eficientă pentru un număr mic de elemente ( mai puţin de 15), dar nu pentru tabele mari. Nu necesită foarte multă memorie, dar este de două ori mai lentă decât InsertionSort în aproape orice situaţie. Timpul de execuţie depinde de input, adică de ordinea iniţială a elementelor. Dacă tabela este déjà sortată e nevoie de un singur pas, adică n-1 comparări. În cazul cel mai nefavorabil sunt necesare n*(n-1)/2 comparări şi n*(n-1)/2 interschimbări. Performanţa algoritmului în caz general este mai greu de analizat dar este asemănător cazului nefavorabil. Algoritmul în C++ este:

void BubbleSort(Tip a[Nmax+1],int Size)

{

for(int i=0;i<Size;i++)

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

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

{

Tip aux=v[i];

a[i]=a[j];

a[j]=aux;

}

}

SelectionSort

Selectia direcă este una dintre cele mai simple metode de sortare şi va lucra foarte bine pentru tabele mici, fiecare element, este mutat cel mult o singură dată. Algoritmul presupune ca la fiecare pas”i” să se găsească elementul minim dintre a[i+1], a[i+2]...a[n] şi se interschimbă cu [i]. Se cheltuie cel mai mult timp cu căutarea elementului minim din partea nesortată a tabelei. Căutarea se face de la stânga la dreapta. Pe parcursul fiecărui pas este necesar o interschimbare, deci numărul interschimbărilor pentru n elemente este: n-1. Numărul total al comparărilor este:

Algoritmul în C++ este:

Selection (type a[], int size)

{

int i, j;

type min, t;

For ( i=1; i<=size-1; i++ )

{

min = a[i];

For ( j = i+1; j<= size; j++ )

If ( a[j]<min ) min = a[j];

If (a[i]>min) t =a[min]; a[min]=a[i]; a[i]=t;

}

}

InsertionSort

Inserţia directă aparţine familiei de tehnici de sortare care se bazează pe metoda „jucătorului de bridge”. Este un algoritm aproape la fel de simplu ca Selection Sort, dar poate mai flexibil. Considerăm elementele a[1]…a[i-1] fiind sortate, înserăm elementul a[i] în locul cei revine.

Fiind dat o tabelă a cu n elemente nesortate, parcurgem tabela şi le inserăm fiecare element în locul propriu între celelalte elemente considerate sortate. Pentru fiecare i=2…n, elementele a[1]….a[i] sunt sortate prin inserarea lui a[i] între lista elementelor sortate a[1]….a[i-1]. Elementele aflate în stânga indexului sunt în ordine sortată dar nu sunt în poziţia lor finală. Tabela este sortată complet când indexul ajunge la capătul drept al tabelei. Insertion sort este un algoritm de sortare simplu. Timpul de execuţie al algoritmului depinde de numărul inversărilor, deci de ordine initial al elementelor. În cazul cel mai nefavorabil, când tabela este iniţial sortată în ordine inversă mutarea elementelor se realizează de

ori.

Algoritmul în C++ este:

Insertion ( type A[ ], int size )

{

int i, j;

type v;

For ( i = 2; i <= size; i++ )

{

v = A[i]; j = i;

While ( A[j-1] > v )// mut elementele cu o pozitie in fata

{ A[j] = A[j-1]; j --; }

A[j] = v;// pun elem in poz lui

}

}