Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.
Ambele părți revizuirea anterioară Versiuni anterioare Urmatoarea versiune | Versiuni anterioare Urmatoarea versiune Ambele părți următoarea reviziune | ||
laboratoare:laborator-02 [2017/02/14 20:55] florina_elena.barbu |
laboratoare:laborator-02 [2018/02/25 21:32] mihai.iacov |
||
---|---|---|---|
Linia 1: | Linia 1: | ||
- | ====== Laborator 02: Liste & Hashtable | + | ====== Laborator 02: Algoritmi de sortare 1 ====== |
- | \\ | + | |
- | =====1 Obiectivele laboratorului===== | + | |
- | *Înțelegerea conceptului de funcționare și implementarea unor liste dublu înlănțuite și circulare | + | |
- | *Implementarea unor funcții individuale de lucru cu aceste structuri de date. | + | |
- | \\ | + | |
- | =====2 Ce este o listă?===== | + | =====1. Obiectivele laboratorului===== |
- | ====2.1 Definiție==== | + | |
- | Listele sunt cele mai bune și cele mai simple exemple a unei structuri de date dinamice care folosește pointeri | + | |
- | la implementarea sa.în mod esențial, trebuie înțeles că listele funcționează ca un vector care se poate mări sau | + | |
- | micșora după nevoie, din orice punct al mulțimii sale de elemente. | + | |
- | #POZA 1# | + | Propunem studierea următorilor algoritmi de sortare: |
+ | * Bubble Sort | ||
+ | * Selection Sort | ||
+ | * Insertion Sort | ||
+ | * Merge Sort | ||
+ | * Quick Sort | ||
- | Avantaje ale utilizării listelor: | + | =====2. Introducere===== |
- | *Elementele pot fi adăugate sau șterse din mijlocul listei | + | |
- | *Nu trebuie definită o mărime inițială, iar memoria se alocă pe rând, odată cu fiecare element adăugat | + | |
- | Definirea nodului unei liste: | + | ====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ă**, | ||
+ | |||
+ | Exemplu: dacă alegem drept cheie un atribut **număr întreg** şi relaţia **mai mic sau egal**(< | ||
+ | |||
+ | 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 | ||
+ | | ||
+ | | ||
+ | |||
+ | Folosim notaţia O(n) pentru a indica: | ||
+ | *un număr de operaţii de ordinul lui n. În acest caz, spunem că avem " | ||
+ | *o dimensiune de ordinul lui n pentru memoria alocată. În acest caz, spunem că avem " | ||
+ | |||
+ | |||
+ | ====2.2 Metodele de sortare folosite==== | ||
+ | |||
+ | Fiecare algoritm se bazează pe o metodă de sortare: | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | |||
+ | |||
+ | =====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. | ||
+ | |||
+ | | ||
+ | fiind comparate elementele alăturate **a[i] si a[i+1]**. Dacă vor fi găsite 2 elemente neordonate, | ||
+ | valorile lor vor fi interschimbate. | ||
+ | | ||
+ | elemente neordonate. | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | ===Implementare :=== | ||
<file cpp> | <file cpp> | ||
- | typedef struct node{ | + | //sortare descrescatoare |
- | | + | void bubble(int a[],int n) |
- | struct node * next; | + | { |
- | }node t; | + | int i, |
+ | do { | ||
+ | schimbat = 0; | ||
+ | // parcurgem vectorul | ||
+ | for(i = 0; i < n-1; i++) { | ||
+ | | ||
+ | if (a[i] < a[i+1]) { | ||
+ | // interschimbare | ||
+ | aux = a[i]; | ||
+ | a[i] = a[i+1]; | ||
+ | a[i+1] = aux; | ||
+ | schimbat = 1; | ||
+ | | ||
+ | } | ||
+ | } while(schimbat); | ||
+ | } | ||
</ | </ | ||
- | ====2.2 Clasificare==== | + | ====3.2 Selection sort==== |
- | * **Liste simplu înlănțuite** - Elementele au o singură legătură către următorul element introdus, iar ultimul | + | |
- | element pointează către NULL. | + | |
- | #Poza liste simplu inlantuite# | + | * timp mediu: O(N^2) |
+ | * timp la limită: O(N^2) | ||
+ | * memorie: O(1) | ||
+ | * Stabil: DA | ||
- | * **Liste dublu înlănțuite** - Elementele au dublă legătură către precedentul și antecedentul, capul listei pointând | + | ===Descriere :=== |
- | spre NULL și ultimul element de asemenea | + | Acest algoritm selectează, |
+ | i până la n).Valoarea minimă găsită la pasul i este pusă în vector la poziţia | ||
+ | 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**. | ||
+ | {{ : | ||
- | #Poza lista dublu inlantuite# | + | ===Implementare :=== |
+ | <file cpp> | ||
+ | void selectionSort(int a[],int n) | ||
+ | { | ||
+ | int i, | ||
+ | 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]; // | ||
+ | a[minPoz] = aux; | ||
+ | } | ||
+ | } | ||
+ | </ | ||
- | * **Liste circulare** - Pot fi simplu sau dublu înlănțuite | + | ====3.3 Insertion sort==== |
+ | |||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | |||
+ | ===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ă. | ||
+ | | ||
+ | imaginar în două părţi - o parte sortată şi o parte nesortată. La început, partea sortată conţine | ||
+ | primul | ||
+ | *La fiecare pas, algoritmul ia primul | ||
+ | | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | ===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]; // | ||
+ | a[j] = a[j - 1]; | ||
+ | a[--j] = aux; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | ====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, | ||
+ | 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. | ||
+ | | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | ===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)/ | ||
+ | merge(a,st, m); | ||
+ | merge(a, | ||
+ | mergeSort(a, | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | ====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, | ||
+ | |||
+ | Algoritmul se bazează pe următorii paşi: | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | |||
+ | < | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | ===Implementare :=== | ||
+ | <file cpp> | ||
+ | void qSort(int a[],int st,int dr) | ||
+ | { | ||
+ | int temp, | ||
+ | mijl = a[st+(dr-st)/ | ||
+ | min = st; max = dr; | ||
+ | do | ||
+ | { | ||
+ | while(a[min] < mijl) min++; | ||
+ | while(a[max] > mijl) max--; | ||
+ | if(min <= max) // | ||
+ | { | ||
+ | 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, | ||
+ | if(dr > min) qSort(a, | ||
+ | } | ||
+ | </ | ||
- | #Poza lista circulare# | + | ===== 4. Exerciţii ===== |
- | ====2.3 Operații | + | E0. Alegeţi un algoritm A(dintre Bubble, Insertion şi Selection) şi un algoritm B(dintre Merge şi Quick). Introduceţi nişte variabile globale |
- | *Adăugare la începutul listei | + | |
- | *Adăugare la sfârsitul listei | + | |
- | *Adăugarea înainte sau după un element dat | + | |
- | *Ștergerea capului | + | |
- | *Ștergerea unui element oarecare din listă | + | |
+ | E1. Implementaţi un algoritm(dintre Bubble, Insertion şi Selection) pentru sortarea unui vector cu n cuvinte de maxim 4 litere fiecare. | ||
- | =====3.Exerciții propuse pentru laborator===== | + | E2. Implementaţi un algoritm(dintre Merge şi Quick) pentru sortarea unui vector de structuri, unde fiecare structură reprezintă un moment de timp(int ora,min,sec). |
- | 1.// | + | |
- | Scrieți funcțiile care să scrie urmatoarele: | + | E3. Se dă un vector |
- | //[0.5p]//Să introducă un nou angajat după al treilea.\\ | + | |
- | // | + | |
- | //[0.75p]//Să steargă angajatul cu un anumit număr de telefon introdus.\\ | + | |
+ | <note tip>Este uşor să verificăm dacă două elemente sunt în ordine atunci când elementele au o structură simplă. Dacă avem o structură mai complicată, | ||
+ | Puteţi utiliza următorul model pentru exerciţiile propuse: {{ : | ||
+ | ===== 4. Exerciţii de laborator (Linux) ===== | ||
+ | Pentru acest laborator puteți descărca scheletul de cod de [[http:// | ||
+ | === Linux=== | ||
+ | Puteti folosi utilitarul '' | ||
+ | * '' | ||
+ | * '' | ||
+ | Pentru compilare folositi comanda '' | ||