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 | ||
laboratoare:laborator-02 [2017/03/02 20:51] iulian.matesica [4. Exercitii Liste] |
laboratoare:laborator-02 [2018/02/25 22:02] (curent) mihai.iacov [2.2 Caracterizarea unui algoritm] |
||
---|---|---|---|
Linia 1: | Linia 1: | ||
- | ====== Laborator 02: Liste ====== | + | ====== 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. | + | |
- | {{ :laboratoare: | + | 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 | + | ==== 2.1 Calculul complexităţii algoritmilor ==== |
+ | |||
+ | Analiza complexității unui algoritm are ca scop estimarea volumului de resurse de calcul necesare pentru execuția algoritmului. Prin resurse se înțelege: | ||
+ | • //Spațiul de memorie// necesar pentru stocarea datelor pe care le prelucrează algoritmul.\\ | ||
+ | • //Timpul necesar pentru execuția// tuturor prelucrărilor specificate în algoritm. | ||
+ | |||
+ | Această analiză este utilă pentru a stabili dacă un algoritm utilizează un volum acceptabil de resurse pentru rezolvarea | ||
+ | |||
+ | Este așadar suficient sa se contorizeze doar anumite tipuri de operații elementare, | ||
+ | |||
+ | **Exemplul 1 - Suma a n numere** \\ | ||
+ | Consideram problema calculului sumei . Dimensiunea acestei probleme poate fi considerata // | ||
+ | problemei. | ||
+ | {{ : | ||
+ | |||
+ | |||
+ | **Exemplul 2 - Înmulțirea a 2 matrici** \\ | ||
+ | Consideram problema determinarii produsului a doua matrici: A de dimensiune m×n si B de dimensiune n×p. In acest caz dimensiunea problemei este determinata de trei valori: (m, n, p). \\ | ||
+ | In practica nu este necesara o analiza atat de detaliata ci este suficient sa se identifice | ||
+ | operatia dominantă si sa se estimeze numarul de repetari ale acesteia. Prin operatie dominanta se ıntelege operatia care contribuie cel mai mult la timpul de executie a algoritmului si de regulă este operatia ce apare ın ciclul cel mai interior. În exemplul | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | ---- | ||
+ | |||
+ | ====2.2 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 " | ||
+ | |||
+ | <note important> | ||
+ | În acest material se face abuz de notaţie. **NU** confundaţi cu notaţiile **Big-O (O)**, **Big-Omega (Ω)**, **Big-Theta (θ)**. De fapt, notaţia din acest material " | ||
+ | </ | ||
+ | |||
+ | ====2.3 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 | + | //sortare descrescatoare |
- | | + | void bubble(int a[],int n) |
- | 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. | + | |
- | {{ :laboratoare: | + | * timp mediu: O(N^2) |
+ | * timp la limită: O(N^2) | ||
+ | * memorie: O(1) | ||
+ | * Stabil: DA | ||
+ | ===Descriere :=== | ||
+ | Acest algoritm selectează, | ||
+ | i până la n).Valoarea minimă găsită la pasul i este pusă în vector la poziţia i, | ||
+ | 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**. | ||
+ | {{ : | ||
- | * **Liste dublu înlănțuite** - Elementele au dublă legătură către precedentul și antecedentul, capul listei pointând | + | ===Implementare :=== |
- | spre NULL și ultimul element | + | <file cpp> |
+ | void selectionSort(int a[], | ||
+ | { | ||
+ | int i,j, | ||
+ | for(i = 0; i < n - 1;i++) | ||
+ | { | ||
+ | minPoz = i; | ||
+ | min = a[i]; | ||
+ | for(j = i + 1;j < n;j++) //selectam minimul | ||
+ | //din vectorul ramas( | ||
+ | { | ||
+ | if(min > a[j]) //sortare crescatoare | ||
+ | { | ||
+ | minPoz = j; //pozitia elementului minim | ||
+ | min = a[j]; | ||
+ | } | ||
+ | } | ||
+ | aux = a[i] ; | ||
+ | a[i] = a[minPoz]; // | ||
+ | a[minPoz] = aux; | ||
+ | } | ||
+ | } | ||
+ | </ | ||
- | {{ : | + | ====3.3 Insertion sort==== |
- | * **Liste circulare** - Pot fi simplu sau dublu înlănțuite cu proprietatea că ultimul element pointează spre primul. | + | |
+ | | ||
+ | | ||
+ | | ||
- | {{ :laboratoare: | + | ===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 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. | ||
+ | | ||
- | ====2.3 Operații cu liste:==== | + | {{ :laboratoare: |
- | *Adăugare la începutul listei | + | |
- | *Adăugare la sfârsitul listei | + | |
- | *Adăugarea înainte sau după un element dat | + | |
- | *Ștergerea capului de listă | + | |
- | *Ștergerea unui element oarecare din listă | + | |
+ | ===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.Exerciții propuse pentru laborator===== | + | ====3.4 Merge sort==== |
- | 1. Creați o listă circulară, | + | |
- | * Scrieți funcțiile care să scrie urmatoarele: | + | |
- | * Să introducă un nou angajat după al treilea.\\ | + | |
- | * Să introducă un nou angajat inainte de cel care e " | + | |
- | * Să steargă angajatul cu un anumit număr de telefon introdus.\\ | + | |
- | 2. Să se creeze o listă liniara simplu inlantuita care contine elemente intregi citite dintr-ul fisier text. | + | * timp mediu: O(N log N) |
- | Se citeste apoi o valoare intreaga x. Sa se stearga primul nod care contine valoarea x. | + | * timp la limită: O(N log N) |
- | Fișierul se va da ca parametru în linia de comandă. | + | * memorie: O(N) |
+ | * Stabil: DA | ||
- | 3.Sa se construiasca o lista liniara simplu inlantuita cu elemente numere intregi. Să se afișeze și apoi să se stearga | + | ===Descriere :=== |
+ | În cazul sortării prin interclasare, | ||
+ | din acelaşi vector. | ||
+ | Sortarea prin interclasare utilizează metoda **Divide et Impera**: | ||
- | =====4. Exercitii Liste ===== | + | *se împarte vectorul în secvenţe din ce în ce mai mici, astfel încât fiecare secvenţă să fie |
- | Pentru laboratorul de liste inlantuite vom porni de la o arhiva | + | ordonată la un moment dat şi interclasată cu o altă secvenţă din vector corespunzătoare. |
+ | *practic, interclasarea va începe când se ajunge | ||
- | Descarcati arhiva de aici si dezarhivati-o. Puteti folosi utilitarul '' | + | {{ : |
- | <code bash> | + | |
- | student@sda-ab-vm:~/ | + | |
- | --2017-03-02 20:45:55-- | + | |
- | Resolving elf.cs.pub.ro (elf.cs.pub.ro)... 141.85.227.116 | + | |
- | Connecting to elf.cs.pub.ro (elf.cs.pub.ro)|141.85.227.116|: | + | |
- | HTTP request sent, awaiting response... 200 OK | + | |
- | Length: 2368 (2,3K) [application/ | + | |
- | Saving to: ‘lab1-skel.zip’ | + | |
- | lab1-skel.zip | + | ====3.5 Quick sort==== |
- | 2017-03-02 20:45:56 (4,78 MB/s) - ‘lab1-skel.zip’ saved [2368/2368] | + | * timp mediu: O(N log N) |
+ | * timp la limită: O(N^2) | ||
+ | * memorie: O(log N) | ||
+ | * Stabil: NU | ||
- | student@sda-ab-vm:~/ | + | ===Descriere |
- | lab1-skel.zip | + | Quick Sort este unul dintre cei mai rapizi şi mai utilizaţi algoritmi de sortare până în acest moment, |
- | student@sda-ab-vm: | + | |
- | Archive: | + | |
- | inflating: list.c | + | |
- | inflating: list.h | + | |
- | inflating: Makefile | + | |
- | student@sda-ab-vm: | + | |
- | gcc list.c -o list -std=gnu99 | + | |
- | student@sda-ab-vm: | + | |
- | </ | + | |
- | Pentru compilare folositi comanda '' | + | Algoritmul se bazează pe următorii paşi: |
+ | *alegerea unui element pe post de **pivot** | ||
+ | | ||
+ | | ||
+ | | ||
+ | < | ||
+ | {{ : | ||
+ | ===== 4. Exerciţii ===== | ||
- | ====Probleme opţionale - de interviu==== | + | 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 cu care să contorizaţi numărul |
- | 1. Se dă o listă simplu înlănţuită(primiţi doar un pointer către primul element). Verificaţi dacă lista conţine o buclă. (o listă simplu înlănţuită conţine o buclă => niciun element nu are legătura NULL) | + | E1. Implementaţi un algoritm(dintre Bubble, Insertion şi Selection) pentru sortarea unui vector cu n cuvinte de maxim 4 litere fiecare. |
- | 2. Se dau două liste(pentru fiecare | + | E2. Implementaţi un algoritm(dintre Merge şi Quick) |
- | 3. Se dă o listă | + | E3. Se dă un vector de n întregi, |
- | ====== Extra: Hashtable(tabela | + | <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ă, |
- | =====1 Introducere===== | + | Puteţi utiliza următorul model pentru exerciţiile propuse: {{ : |
- | (De urmărit ideea din introducere şi funcţia de indexare) | + | ===== 5. Exerciţii de laborator (Linux) ===== |
+ | Pentru acest laborator puteți descărca scheletul de cod de [[http:// | ||
- | ====1.1 Poveste==== | + | === Linux=== |
+ | Puteti folosi utilitarul '' | ||
- | ===Să presupunem urmatoarele detalii dintr-un caz real:=== | + | * '' |
+ | * '' | ||
- | | + | Pentru compilare folositi comanda '' |
- | |