1

60

2. Algoritmi de sortare (clasici)

n acest capitol vom prezenta civa algortimi de sortare (ordonare) dintre cei mai reprezentativi i mai des utilizai.

2.1. Sortare prin selecie directAceast metod se bazeaz pe urmtorul principiu, de exemplu pentru ordonare cresctoare:1.Se selecteaz termenul cu cea mai mic valoare.

2.Se schimb acesta cu primul termen (ai).

Apoi se repet operaiile cu cele n-1 elemente rmase, i aa mai departe pn rmne un singur termen (cel mai mare). Deci, pentru sortarea cresctoare a unui ir, algoritmul este urmtorul:for (i = 1; i < n-1; i++) {* se determin indicele celui mai mic element, k, dintre a[i], . . . ,a[n]; * se interschimb a[i] cu a[k];}Iat ntreg programul care sorteaz prin selecie direct:/* sel_dir.c - programul ordoneaza un vector prin selectie directa, utilizand pentru aceasta determinarea minimului si a pozitiei lui, la fiecare iteratie si realizand o singura inversiune intre acest minim si valoarea a[i], corespunzatoare iteratiei curente; se determina si numarul de comparatii si inversiuni realizate */#include#include int ncomp=0, ninv=0; /* numar de comparatii si inversiuni */void sort_sel_direct ( double a[], int n )/* functia sorteaza un vector prin metoda de selectie directa */{double x;int i, j, k;for ( i = 0 ; i < n-1 ; ++i ){k = i;/* initializare indice, k, si elementul minim, x */x = a[i];for ( j = i+1 ; j < n ; ++j, ncomp++ ) /* determinare minim si indicele lui din sir */if (a[j] < x){k = j;x = a[k];}a[k] = a[i];/* interschimbare minim cu primul din subsirul sursa, */a[i] = x;/* adica cu primul din subsirul neordonat */ninv++;}}void main(void){ double sir[100]; int ne,i, nl=0; clrscr(); printf("Numar elemente:"); scanf("%d",&ne); for(i=0;i