Algoritmide sortare

Programarea Calculatoarelor şi Limbaje de Programare 1

http://www.eed.usv.ro/~vatavu 1/26

Algoritmi de Sortare

Radu-Daniel Vatavu

Facultatea de Inginerie Electrică şi Ştiinţa Calculatoarelor Universitatea „Ştefan cel Mare” Suceava http://www.eed.usv.ro/~vatavu



Sortarea este o operaţie fundamentală constând în ordonarea unei mulţimi de elemente A în funcţie de o relaţie de ordine R.

Exemplu

A = {71, 12, 25, 53, 42} Mulţimea A sortată crescător va fi {12, 25, 42, 53, 71} unde R este relaţia de ordine pe mulţimea numerelor reale.

A = {„student”, „elev”, „studenţie”, „facultate”} Mulţimea A sortată crescător va fi {„elev”, „facultate”, „student”, „studenţie”} unde R este relaţia de ordine lexicografică (dicţionar).



Numim relaţie de ordine totală R peste o mulţime A acea relaţie care respectă proprietăţile: � a R a (reflexivitatea) � dacă a R b şi b R a atunci a = b (identitatea) � a R b şi b R c atunci a R c (tranzitivitatea)

Acba ∈∀ ,,

Definiţie

Se numeşte algoritm de sortare acel algoritm care determină o permutare P a mulţimii {0, 1, … n-1} astfel încât

)(iPa R )( jPa 10 −≤≤≤∀ nji .



Exemplu

n = 5

a 71 12 25 53 42

0 1 2 3 4

Un algoritm de sortare va furniza permutarea {1, 2, 4, 3, 0} pentru care avem elementele şirului a în ordine crescătoare:

a 12 25 42 53 71

0 1 2 3 4



În practică, elementele ce trebuie ordonate sunt rareori valori izolate ci reprezintă elemente dintr-o colecţie de date denumită articol.

Fiecare articol conţine o cheie care este valoarea ce trebuie ordonată iar restul articolului conţine date adiţionale.

Exemplu

� Ordonăm o mulţime de studenţi în funcţie de nota obţinută la disciplina PCLP1.

� Ordonăm o serie de evenimente istorice în funcţie de anul în care au avut loc.



Aplicaţii ale sortării:

� Punerea în corespondenţă a articolelor din două sau mai multe mulţimi (liste, fişiere, zone de memorie)

� Sortarea este un pas intermediar în multe aplicaţii (căutarea şi regăsirea informaţiei – algoritmul de căutare binară)

� Prezentarea datelor



Sortarea poate fi: � internă (în memoria calculatorului) � externă (în fişiere, date mari) Algoritmii de sortare: � în-loc (folosesc aceeaşi zonă de memorie) � este folosită memorie adiţională



Performaţa unui algoritm de sortare: � numărul de operaţii efectuate � memoria folosită

void Sorteaza(int n, int a[])

{

...

}



Sortarea prin selecţie

Pas #1: Determinarea valorii minime din şir Pas #2: Interschimbăm valoarea minimă cu valoarea aflată la începutul şirului. Repetăm paşii 1-2 pentru restul elementelor din şir (exceptând valoarea minimă tocmai selectată).

Exemplu



int DeterminaMinim(int n, int a[])

{

1 int i;

2

3 int min = a[0];

4 for(i = 1; i < n; i++)

5 if (min > a[i])

6 min = a[i];

7

8 return min;

}



int DeterminaMinim(int n, int a[])

{

1 int i;

2

3 int poz_min = 0;

4 for(i = 1; i < n; i++)

5 if (a[poz_min] > a[i])

6 poz_min = i;

7

8 return poz_min;

}

int poz = DeterminaMinim(n, a);

printf(“Valoarea minimă se află pe poziţia %d şi

este %d”, poz, a[poz]);



int DeterminaMinim(int n, int a[], int l, int r)

{

1 int i;

2

3 int poz_min = l;

4 for(i = l; i <= r; i++)

5 if (a[poz_min] > a[i])

6 poz_min = i;

7

8 return poz_min;

}



void SorteazaPrinSelectie(int n, int a[])

{

1 int i;

2 for(i = 0; i < n; i++)

3 {

4 int poz_min = DeterminaMinim(n, a, i, n - 1);

5 if (poz_min != i)

6 {

7 int temp = a[poz_min];

8 a[poz_min] = a[i];

9 a[i] = temp;

10 }

11 }

}



void main()

{

1 int a[] = {12, 25, 42, 71, 53};

2 int n = sizeof(a) / sizeof(int);

3

4 SorteazaPrinSelectie(n, a);

5 Afisare(n, a);

}



Observaţie: sortarea poate fi realizată şi prin determinarea valorii maxime din şir.

void SorteazaPrinSelectie2(int n, int a[])

{

1 int i;

2 for(i = n-1; i >= 0; i--)

3 {

4 int poz_max = DeterminaMaxim(n, a, 0, i);

5 if (poz_max != i)

6 {

7 int temp = a[poz_max];

8 a[poz_max] = a[i];

9 a[i] = temp;

10 }

11 }

}



Sortarea prin selecţie:

� Metodă bazată pe comparaţii între elemente � Poate fi aplicată pentru orice mulţime pentru care avem o relaţie de ordine R

� Este o metodă de sortare în-loc (nu foloseşte memorie suplimentară)



Sortarea prin numărare (distribuţie)

Are drept punct de plecare relaţia de ordine pe mulţime numerelor întregi. Foloseşte un spaţiu de memorie suplimentar de dimensiune M suficientă pentru a acoperi plaja de valori a mulţimii A.

Pentru element Aai ∈ vom număra apariţiile sale în mulţimea A în spaţiul de memorie suplimentar la poziţia ia . Echivalent, elementele Aai ∈ sunt distribuite în spaţiul de memorie suplimentar.



#define MAX 100

void SorteazaPrinNumarare(int n, int a[])

{

1 int nr[MAX];

2 int i;

3

4 for(i = 0; i < MAX; i++) nr[i] = 0;

5 for(i = 0; i < n; i++) nr[a[i]]++;

6

7 n = 0;

8 for(i = 0; i < MAX; i++)

9 while(nr[i] > 0)

10 {

11 a[n++] = i;

12 nr[i]--;

13 }

}



void main()

{

1 int a[] = {12, 25, 42, 71, 53};

2 int n = sizeof(a) / sizeof(int);

3

4 SorteazaPrinNumarare(n, a);

5 Afisare(n, a);

}



Sortarea prin numărare:

� Nu este bazată pe comparaţii între elemente ci foloseşte relaţia de ordine a numerelor întregi

� Poate fi aplicată pentru chei aparţinând mulţimii numerelor întregi (algoritmul prezentat funcţionează doar pentru chei pozitive)

� Nu este o metodă de sortare în-loc (foloseşte memorie suplimentară)



Sortarea lexicografică

Constă în ordonarea elementelor unei mulţimi de şiruri de caractere având la bază relaţia de ordine lexicografică (ordine de dicţionar).

Exemplu

„mere” < „pere” „marmeladă” < „mere” „marmeladă” < „marmotă”



int strcmp(const char *s1, const char *s2);

< 0 s1 < s2

== 0 s1 = s2

> 0 s1 > s2

printf(“%d”, strcmp(”marmeladă”, ”mere”));

char* strcpy(char *dest, const char *src);

char s1[] = “primul sir”;

char s2[] = “al doilea sir”;

strcpy(s1, s2);

printf(“%s %s”, s1, s2);



#define MAX 30

void SorteazaCuvinte(int n, char cuvinte[][MAX])

{

1 int i;

2 int sortat = 0;

3

4 do

5 {

6 sortat = 1;

7 for(i = 0; i < n - 1; i++)

8 if (strcmp(cuvinte[i], cuvinte[i+1]) > 0)

9 {

10 char temp[MAX];

11 strcpy(temp, cuvinte[i]);

12 strcpy(cuvinte[i], cuvinte[i + 1]);

13 strcpy(cuvinte[i + 1], temp);

14

15 sortat = 0;

16 }

17 }while(!sortat);

}



void main()

{

1 char cuvinte[][MAX] = {

2 "costel",

3 "george",

4 "ionut",

5 "vasile",

6 "mihai"

7 };

8 int n = sizeof(cuvinte)/sizeof(char [MAX]);

9

10 AfiseazaCuvinte(n, cuvinte);

11 SorteazaCuvinte(n, cuvinte);

12 AfiseazaCuvinte(n, cuvinte);

13

14 getch();

}



void AfiseazaCuvinte(int n, char cuvinte[][MAX])

{

1 int i;

2 for(i = 0; i < n; i++)

3 printf("%s, ", cuvinte[i]);

4 printf("\n");

}



Sortarea prin inserţie void SorteazaPrinInsertie(int n, int a[])

{

1 int i, j;

2

3 for(i = 1; i < n; i++)

4 {

5 int cheie = a[i];

6 j = i - 1;

7 while(cheie < a[j] && j >= 0)

8 {

9 a[j + 1] = a[j];

10 j--;

11 }

12 a[j + 1] = cheie;

13 }

}

Algoritmide sortare

Documents

Transcript of Algoritmide sortare