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-08 [2017/02/23 18:56] mihai.iacov [3.5 Quick sort] |
laboratoare:laborator-08 [2017/04/20 20:53] iulian.matesica [4. Exerciţii] |
||
---|---|---|---|
Linia 59: | Linia 59: | ||
| | ||
elemente neordonate. | elemente neordonate. | ||
+ | |||
+ | {{ : | ||
===Implementare :=== | ===Implementare :=== | ||
Linia 65: | Linia 67: | ||
void bubble(int a[],int n) | void bubble(int a[],int n) | ||
{ | { | ||
- | int i, | + | |
- | do | + | do { |
- | { | + | schimbat = 0; |
- | schimbat = 0; | + | // parcurgem vectorul |
- | for(i = 0; i < n-1; i++) //parcurgem vectorul | + | |
- | if(a[i] < a[i+1]) | + | |
- | //mai mica decat cea de pe pozitia i+1 | + | if (a[i] < a[i+1]) |
- | { // | + | |
- | aux = a[i]; | + | |
- | a[i] = a[i+1]; | + | a[i] = a[i+1]; |
- | a[i+1] = aux; | + | a[i+1] = aux; |
- | schimbat = 1; | + | schimbat = 1; |
- | } | + | } |
- | }while(schimbat); | + | |
+ | } while(schimbat); | ||
} | } | ||
</ | </ | ||
Linia 94: | Linia 97: | ||
intereschimbarea cu poziţia actuală a minimului.Nu este un algoritm indicat pentru vectorii | 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**. | mari, în majoritatea cazurilor oferind rezultate mai slabe decât **insertion sort** şi **bubble sort**. | ||
+ | {{ : | ||
===Implementare :=== | ===Implementare :=== | ||
Linia 136: | Linia 140: | ||
*La fiecare pas, algoritmul ia primul element din partea nesortată şi il inserează în locul potrivit al părţii sortate. | *La fiecare pas, algoritmul ia primul element din partea nesortată şi il inserează în locul potrivit al părţii sortate. | ||
| | ||
+ | |||
+ | {{ : | ||
===Implementare :=== | ===Implementare :=== | ||
Linia 149: | Linia 155: | ||
aux = a[j]; // | aux = a[j]; // | ||
a[j] = a[j - 1]; | a[j] = a[j - 1]; | ||
- | a[j--] = aux; | + | a[--j] = aux; |
} | } | ||
} | } | ||
Linia 170: | Linia 176: | ||
ordonată la un moment dat şi interclasată cu o altă secvenţă din vector corespunzătoare. | ordonată la un moment dat şi interclasată cu o altă secvenţă din vector corespunzătoare. | ||
| | ||
+ | |||
+ | {{ : | ||
===Implementare :=== | ===Implementare :=== | ||
Linia 221: | Linia 229: | ||
< | < | ||
+ | |||
+ | {{ : | ||
===Implementare :=== | ===Implementare :=== | ||
Linia 245: | Linia 255: | ||
} | } | ||
</ | </ | ||
+ | |||
+ | ===== 4. Exerciţ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 cu care să contorizaţi numărul de **comparaţii** pentru algoritmii A şi B. Comparaţi rezultatele pentru un vector de întregi de lungime n = 20. | ||
+ | |||
+ | E1. Implementaţi un algoritm(dintre Bubble, Insertion şi Selection) pentru sortarea unui vector cu n cuvinte de maxim 4 litere fiecare. | ||
+ | |||
+ | 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, | ||
+ | |||
+ | E3. Se dă un vector de n întregi, iar toate valorile din vector sunt între 0 şi 1000. Sortaţi vectorul în timp O(n). | ||
+ | |||
+ | <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 '' | ||