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 13:40] mihai.iacov [3.1 Quick sort] |
laboratoare:laborator-08 [2017/04/19 22:48] iulian.matesica [3.5 Quick sort] |
||
---|---|---|---|
Linia 28: | Linia 28: | ||
Folosim notaţia O(n) pentru a indica: | Folosim notaţia O(n) pentru a indica: | ||
*un număr de operaţii de ordinul lui n. În acest caz, spunem că avem " | *un număr de operaţii de ordinul lui n. În acest caz, spunem că avem " | ||
- | *o dimensiune de ordinul n pentru memoria alocată. În acest caz, spunem că avem " | + | *o dimensiune de ordinul |
Linia 149: | Linia 149: | ||
aux = a[j]; // | aux = a[j]; // | ||
a[j] = a[j - 1]; | a[j] = a[j - 1]; | ||
- | a[j--] = aux; | + | a[--j] = aux; |
} | } | ||
} | } | ||
Linia 162: | Linia 162: | ||
* Stabil: DA | * Stabil: DA | ||
- | Descriere : | + | ===Descriere :=== |
- | In cazul sortarii | + | În cazul sortării |
- | din acelasi | + | din acelaşi |
- | Sortarea prin interclasare | + | Sortarea prin interclasare |
- | - se imparte | + | |
- | ordonata | + | *se împarte |
- | - practic interclasarea va incepe cand se ajunge la o secventa formata | + | ordonată |
- | Aceasta | + | *practic, interclasarea va începe când se ajunge la o secvenţă formată |
- | alcatui in subsir | + | |
- | corespunzator s.a.m.d. | + | ===Implementare :=== |
- | Implementare : | + | |
<file cpp> | <file cpp> | ||
void mergeSort(int a[],int st, int m, int dr) | void mergeSort(int a[],int st, int m, int dr) | ||
Linia 213: | Linia 212: | ||
===Descriere :=== | ===Descriere :=== | ||
- | Quick Sort este unul dintre cei mai rapizi | + | Quick Sort este unul dintre cei mai rapizi |
- | moment,bazandu`se pe tehnica "divide | + | |
- | ,in practica, | + | Algoritmul se bazează pe următorii paşi: |
- | "O(N log N)". | + | |
+ | | ||
+ | | ||
+ | | ||
+ | |||
+ | < | ||
+ | |||
+ | {{ : | ||
===Implementare :=== | ===Implementare :=== | ||
Linia 241: | Linia 247: | ||
} | } | ||
</ | </ | ||
+ | |||
+ | ===== 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: {{ : | ||