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/19 22:51]
iulian.matesica [3.4 Merge sort]
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 94: Linia 96:
 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 139:
  *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 175:
 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 228:
  
 <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 254:
 } }
 </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 |}}
  
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