Sortarea

Extras din referat Cum descarc?

Metodele de sortare se clasifica in metode directe si metode avansate. Metodele directe se bazeaza, pe algoritmi de dificultate redusa, usor de gasit si de inteles. Metodele avansate se bazeaza pe algoritmi putin mai complicati, dar care nu necesita cunostinte de algoritmica. 
Metode directe
Aceasta metoda se rezuma la a compara fiecare element cu celelalte, facandu-se interschimbarea daca elemental mai mare are indexul mai mic. Este cea mai simpli metoda de sortare si nu necesita cunoasterea detaliata a limbajului de programare. Poate fi folosita cu success de incepatori. Bubble sort este o metoda de sortare simpla, eficienta pentru un numar mic de elemente ( mai putin de 15), dar nu pentru tabele mari. Nu necesita foarte multa memorie, dar este de doua ori mai lenta decat InsertionSort in aproape orice situatie. Timpul de executie depinde de input, adica de ordinea initiala a elementelor. Daca tabela este deja sortata e nevoie de un singur pas, adica n-1 comparari. In cazul cel mai nefavorabil sunt necesare n*(n-1)/2 comparari si n*(n-1)/2 interschimbari. Performanta algoritmului in caz general este mai greu de analizat dar este asemanator cazului nefavorabil. Algoritmul in 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 direca este una dintre cele mai simple metode de sortare si va lucra foarte bine pentru tabele mici, fiecare element, este mutat cel mult o singura data. Algoritmul presupune ca la fiecare pas"i" sa se gaseasca elementul minim dintre a[i+1], a[i+2]...a[n] si se interschimba cu [i]. Se cheltuie cel mai mult timp cu cautarea elementului minim din partea nesortata a tabelei. Cautarea se face de la stanga la dreapta. Pe parcursul fiecarui pas este necesar o interschimbare, deci numarul interschimbarilor pentru n elemente este: n-1. Numarul total al compararilor este: 
Algoritmul in 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 
Insertia directa apartine familiei de tehnici de sortare care se bazeaza pe metoda ,,jucatorului de bridge". Este un algoritm aproape la fel de simplu ca Selection Sort, dar poate mai flexibil. Consideram elementele a[1]...a[i-1] fiind sortate, inseram elementul a[i] in locul cei revine. 
Fiind dat o tabela a cu n elemente nesortate, parcurgem tabela si le inseram fiecare element in locul propriu intre celelalte elemente considerate sortate. Pentru fiecare i=2...n, elementele a[1]....a[i] sunt sortate prin inserarea lui a[i] intre lista elementelor sortate a[1]....a[i-1]. Elementele aflate in stanga indexului sunt in ordine sortata dar nu sunt in pozitia lor finala. Tabela este sortata complet cand indexul ajunge la capatul drept al tabelei. Insertion sort este un algoritm de sortare simplu. Timpul de executie al algoritmului depinde de numarul inversarilor, deci de ordine initial al elementelor. In cazul cel mai nefavorabil, cand tabela este initial sortata in ordine inversa mutarea elementelor se realizeaza de 
ori. 
Algoritmul in 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 
} 
}


Fisiere in arhiva (1):

  • Sortarea.doc

Imagini din acest proiect Cum descarc?

Promoție: 1+1 gratis

După plată vei primi prin email un cod de download pentru a descărca gratis oricare alt referat de pe site.Vezi detalii.


Descarcă aceast referat cu doar 4 € (1+1 gratis)

Simplu și rapid în doar 2 pași: completezi adresa de email și plătești. După descărcarea primului referat vei primi prin email un alt cod pentru a descărca orice alt referat.

1. Numele, Prenumele si adresa de email:

Pe adresa de email specificata vei primi link-ul de descarcare, nr. comenzii si factura (la plata cu cardul). Daca nu gasesti email-ul, verifica si directoarele spam, junk sau toate mesajele.

2. Alege modalitatea de plata preferata:


* La pretul afisat se adauga 19% TVA, platibil in momentul achitarii abonamentului / incarcarii cartelei.

Hopa sus!