Aceasta e o versiune anterioară a paginii.
Propunem studierea următorilor algoritmi de sortare:
Numim sortare orice aşezare(sau - mai clar - reaşezare) a unor elemente date în aşa fel încât, după aşezare, să existe o ordine completă în funcţie de un atribut(numit cheie) al elementelor.
Pentru a exista o ordine completă, trebuie să alegem o relaţie pe care vrem sa o impunem. Dacă relaţia este valabilă între oricare două elemente pentru care primul element este aşezat la stânga celui de-al doilea, atunci avem o ordine completă.
Exemplu: dacă alegem drept cheie un atribut număr întreg şi relaţia mai mic sau egal(⇐), obţinem ordinea crescătoare.
Vom descrie un algoritm de sortare prin:
Folosim notaţia O(n) pentru a indica:
Fiecare algoritm se bazează pe o metodă de sortare:
Sortarea prin metoda bulelor se consideră drept una din cele mai puţin efective metode de sortare, dar cu un algoritm mai simplu.
fiind comparate elementele alăturate a[i] si a[i+1]. Dacă vor fi găsite 2 elemente neordonate, valorile lor vor fi interschimbate.
elemente neordonate.
//sortare descrescatoare 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); }
Acest algoritm selectează, la fiecare pas i, cel mai mic element din vectorul nesortat(de la poziţia i până la n).Valoarea minimă găsită la pasul i este pusă în vector la poziţia i,facându-se intereschimbarea cu poziţia actuală a minimului.Nu este un algoritm indicat pentru vectorii mari, în majoritatea cazurilor oferind rezultate mai slabe decât insertion sort şi bubble sort.
void selectionSort(int a[],int n) { int i,j,aux,min,minPoz; for(i = 0; i < n - 1;i++) { minPoz = 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 { minPoz = j; //pozitia elementului minim min = a[j]; } } aux = a[i] ; a[i] = a[minPoz]; //interschimbare a[minPoz] = aux; } }
Spre deosebire de alţi algoritmi de sortare, sortarea prin inserţie este folosită destul de des pentru sortarea tablourilor cu număr mic de elemente. De exemplu, poate fi folosit pentru a îmbunătăţi rutina de sortare rapidă.
imaginar în două părţi - o parte sortată şi o parte nesortată. La început, partea sortată conţine primul element al tabloului şi partea nesortată conţine restul tabloului.
void insertionSort(int a[], int n) { int i, j, aux; for (i = 1; i < n; i++) { j = i; while (j > 0 && a[j - 1] > a[j]) { //cautam pozitia pe care sa mutam a[i] aux = a[j]; //interschimbare a[j] = a[j - 1]; a[j--] = aux; } } }
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 :
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]) 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); } }