Unelte utilizator

Unelte site


laboratoare:laborator-08

Aceasta e o versiune anterioară a paginii.


A PCRE internal error occured. This might be caused by a faulty plugin

====== 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 lui 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 :=== <file cpp> //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); } </file> ====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 :=== <file cpp> 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; } } </file> ====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 :=== <file cpp> 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; } } } </file> ====3.4 Merge sort==== * timp mediu: O(N log N) * timp la limită: O(N log N) * memorie: O(N) * Stabil: DA ===Descriere :=== În cazul sortării prin interclasare, vectorii care se interclasează sunt două secvenţe ordonate din acelaşi vector. Sortarea prin interclasare utilizează metoda **Divide et Impera**: *se împarte vectorul în secvenţe din ce în ce mai mici, astfel încât fiecare secvenţă să fie ordonată la un moment dat şi interclasată cu o altă secvenţă din vector corespunzătoare. *practic, interclasarea va începe când se ajunge la o secvenţă formată din două elemente. Aceasta, odată ordonată, se va interclasa cu o alta corespunzătoare(cu 2 elemente). Cele două secvenţe vor alcătui un subşir ordonat din vector mai mare(cu 4 elemente) care, la rândul lui, se va interclasa cu un subşir corespunzător(cu 4 elemente) ş.a.m.d. ===Implementare :=== <file cpp> 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); } } </file> ====3.5 Quick sort==== * timp mediu: O(N log N) * timp la limită: O(N^2) * memorie: O(log N) * Stabil: NU ===Descriere :=== Quick Sort este unul dintre cei mai rapizi şi mai utilizaţi algoritmi de sortare până în acest moment,bazându-se pe tehnica "**Divide et impera**".Deşi cazul cel mai nefavorabil este O(N^2), în practică, QuickSort oferă rezultate mai bune decât restul algoritmilor de sortare din clasa "O(N log N)". ===Implementare :=== <file cpp> void qSort(int a[],int st,int dr) { int temp,min,max,mijl; mijl = a[st+(dr-st)/2]; //luam mijlocul intervalului min = st; max = dr; do { while(a[min] < mijl) min++; while(a[max] > mijl) max--; if(min <= max) //interschimbare { temp = a[min]; a[min++] = a[max]; a[max--] = temp; } }while(min <= max); //la fiecare pas sortam "mai bine" intervalul st-dr //cand numai avem ce face schimbam intervalul if(st < max) qSort(a,st,max); //crescator if(dr > min) qSort(a,min,dr); //crescator } </file>