Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Ești aici: Structuri de date și algoritmi » Laboratoare » Laborator 08: Drumuri de cost minim
Traseu:
laboratoare:laborator-08

Diferențe

Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.

Link către această vizualizare comparativă

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/25 17:25]
mihai.iacov [3.3 Insertion sort] 		laboratoare:laborator-08 [2017/04/20 20:53]
iulian.matesica [4. Exerciţii]
Linia 59: Linia 59:
  *Parcurgerea tabloului de la stânga spre dreapta se va repeta atât timp cât vor fi întâlnite  *Parcurgerea tabloului de la stânga spre dreapta se va repeta atât timp cât vor fi întâlnite
 elemente neordonate. elemente neordonate.
 +
 +{{ :laboratoare:bubble-sort-example-300px.gif?nolink |}}
  
 ===Implementare :=== ===Implementare :===
Linia 65: Linia 67:
 void bubble(int a[],int n) void bubble(int a[],int n)
 { {
- int i,schimbat,aux; +    int i,schimbat,aux; 
- do +    do { 
- { +        schimbat = 0; 
- schimbat = 0; +        // parcurgem vectorul 
- for(i = 0; i < n-1; i++) //parcurgem vectorul +        for(i = 0; i < n-1; i++) { 
- if(a[i] < a[i+1]) //daca valoarea i din vectorul a este +     // daca valoarea i din vectorul a este mai mica decat cea de pe pozitia i+1 
- //mai mica decat cea de pe pozitia i+1 +            if (a[i] < a[i+1]) {  
- { //interschimbare +                // interschimbare 
- aux = a[i]; +         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);
 } }
 </file> </file>
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**.
 +{{ :laboratoare:selection-sort.gif?nolink |}}
  
 ===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.
  *Când partea nesortată nu mai are nici un element, algoritmul se opreste.  *Când partea nesortată nu mai are nici un element, algoritmul se opreste.
 +
 +{{ :laboratoare:insertion-sort-example-300px.gif?nolink |}}
  
 ===Implementare :=== ===Implementare :===
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.
  *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.  *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.
 +
 +{{ :laboratoare:merge-sort-example-300px.gif?nolink |}}
  
 ===Implementare :=== ===Implementare :===
Linia 221: Linia 229:
  
 <note>Nu există restricţii pentru alegerea pivotului. Algoritmul prezentat alege mereu elementul din mijloc</note> <note>Nu există restricţii pentru alegerea pivotului. Algoritmul prezentat alege mereu elementul din mijloc</note>
 +
 +{{ :laboratoare:sorting_quicksort_anim.gif?nolink |}}
  
 ===Implementare :=== ===Implementare :===
Linia 245: Linia 255:
 } }
 </file> </file>
 +
 +===== 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,min,sec).
 +
 +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ă, atunci este recomandat să definim o funcţie de comparare pe care s-o apelăm pentru verificare, fără a încărca funcţia de sortare.</note>
 +
 +Puteţi utiliza următorul model pentru exerciţiile propuse: {{ :laboratoare:scheletsortare.zip |}}
 +
 +===== 4. Exerciţii de laborator (Linux) =====
 +Pentru acest laborator puteți descărca scheletul de cod de [[http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab8_sortari-skel.zip|aici]]. Descărcați arhiva și dezarhivați-o. 
 +
 +=== Linux===
 +Puteti folosi utilitarul ''%%wget%%'' pentru descarcare si utilitarul ''%%unzip%%'' pentru dezarhivare.
 +
 +  * ''%%wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab8_sortari-skel.zip%%''
 +  * ''%%unzip lab8_sortari-skel.zip%%''
 +
 +Pentru compilare folositi comanda ''%%make%%''. Pentru rulare puteti folosi comanda ''%%make run%%'' sau ''%%./sort%%''.
  
laboratoare/laborator-08.txt · Ultima modificare: 2018/04/23 22:48 de către mihai.iacov

Unelte pagină

Exceptând locurile unde este altfel specificat, conținutul acestui wiki este licențiat sub următoarea licență: CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki