Unelte utilizator

Unelte site


laboratoare:laborator-08

Aceasta e o versiune anterioară a paginii.


Laborator 08: Algoritmi de sortare 1

1. Obiectivele laboratorului

Propunem studierea următorilor algoritmi de sortare:

  • Bubble Sort
  • Selection Sort
  • Insertion Sort
  • Merge Sort
  • Quick Sort

2. Introducere

2.1 Caracterizarea unui algoritm

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:

  • timp mediu - timpul de execuţie la care ne aşteptăm, în medie, pentru sortare
  • timp la limită- timpul de execuţie pentru cel mai rău caz posibil
  • memorie - memoria maximă de care are nevoie algoritmul pentru sortare(excludem memoria deja alocată înainte de algoritm → vectorul efectiv ce va fi sortat)
  • stabilitate - un algoritm stabil păstrează ordinea în care apar două elemente cu aceeaşi cheie(atributul după care sortăm)

Folosim notaţia O(n) pentru a indica:

  • un număr de operaţii de ordinul lui n. În acest caz, spunem că avem „complexitate de timp de ordinul lui n
  • o dimensiune de ordinul n pentru memoria alocată. În acest caz, spunem că avem „complexitate de spaţiu de ordinul lui n

2.2 Metodele de sortare folosite

Fiecare algoritm se bazează pe o metodă de sortare:

  • Bubble sort - interschimbare
  • Selection sort - selecţie
  • Insertion sort - inserare
  • Merge sort - interclasare
  • Quick sort - partiţionare

3. Algoritmii

3.1 Bubble sort

  • timp mediu: O(N^2)
  • timp la limită: O(N^2)
  • memorie: O(1)
  • Stabil: DA

Descriere :

Sortarea prin metoda bulelor se consideră drept una din cele mai puţin efective metode de sortare, dar cu un algoritm mai simplu.

  • Ideea de bază a sortării prin metoda bulelor este în a parcurge tabloul, de la stânga spre dreapta,

fiind comparate elementele alăturate a[i] si a[i+1]. Dacă vor fi găsite 2 elemente neordonate, valorile lor vor fi interschimbate.

  • Parcurgerea tabloului de la stânga spre dreapta se va repeta atât timp cât vor fi întâlnite

elemente neordonate.

Implementare :

//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);
}

3.2 Selection sort

  • timp mediu: O(N^2)
  • timp la limită: O(N^2)
  • memorie: O(1)
  • Stabil: DA

Descriere :

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.

Implementare :

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;
	}
}

3.3 Insertion sort

  • timp mediu: O(N^2)
  • timp la limită: O(N^2)
  • memorie: O(1)
  • Stabil: DA

Descriere :

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ă.

  • Sortarea prin inserţie seamană oarecum cu sortarea prin selecţie. Tabloul este împărţit

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.

  • La fiecare pas, algoritmul ia primul element din partea nesortată şi il inserează în locul potrivit al părţii sortate.
  • Când partea nesortată nu mai are nici un element, algoritmul se opreste.

Implementare :

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;
        }
    }
}

3.2 Merge sort

  • timp mediu: O(N log N)
  • timp la limită: O(N log N)
  • memorie: O(N)
  • Stabil: DA

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);
    }
}

3.1 Quick sort

  • timp mediu: O(N log N)
  • timp la limită: O(N^2)
  • memorie: O(log N)
  • Stabil: NU
laboratoare/laborator-08.1487849869.txt.gz · Ultima modificare: 2017/02/23 13:37 de către mihai.iacov