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/23 18:33]
mihai.iacov [2.1 Caracterizarea unui algoritm] 		laboratoare:laborator-08 [2017/04/19 22:50]
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 149: Linia 154:
             aux = a[j]; //interschimbare             aux = a[j]; //interschimbare
             a[j] = a[j - 1];             a[j] = a[j - 1];
-            a[j--] = aux;+            a[--j] = aux;
         }         }
     }     }
Linia 162: Linia 167:
   * Stabil: DA   * Stabil: DA
  
-Descriere : +===Descriere :=== 
-In cazul sortarii prin interclasare vectorii care se interclaseaza sunt doua secvente ordonate +În cazul sortării prin interclasare, vectorii care se interclasează sunt două secvenţe ordonate 
-din acelasi vector. +din acelaşi vector. 
-Sortarea prin interclasare utilizeaza metoda Divide et Impera: +Sortarea prin interclasare utilizează metoda **Divide et Impera**: 
-- se imparte vectorul in secvente din ce in ce mai mici., astfel incat fiecare secventa sa fie + 
-ordonata la un moment dat si interclasata cu o alta secventa din vector corespunzatoare. + *se împarte vectorul în secvenţe din ce în ce mai mici, astfel încât fiecare secvenţă să fie 
-- practic interclasarea va incepe cand se ajunge la o secventa formata din doua elemente. +ordonată la un moment dat şi interclasată cu o altă secvenţă din vector corespunzătoare. 
-Aceasta odata ordonata se va interclasa cu o alta corespunzatoare. Cele doua secvente vor + *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. 
-alcatui in subsir ordonat din vector mai mare care la randul lui se va interclasa cu subsirul +{{ :laboratoare:merge-sort-example-300px.gif?nolink |}} 
-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 217:
  
 ===Descriere :=== ===Descriere :===
-Quick Sort este unul dintre cei mai rapizi si mai utilizati algoritmi de sortare pana in acest +Quick Sort este unul dintre cei mai rapizi şi mai utilizaţi algoritmi de sortare până în acest moment,bazându-se pe tehnica "**Divide et impera**".Deşi cazul cel mai nefavorabil este O(N^2), în practică, QuickSort oferă rezultate mai bune decât restul algoritmilor de sortare din clasa "O(N log N)". 
-moment,bazandu`se pe tehnica "divide et impera".Desi cazul cel mai nefavorabil este O(N^2) + 
-,in practica,QuickSort ofera rezultate mai bune decat restul algoritmilor de sortare din clasa +Algoritmul se bazează pe următorii paşi: 
-"O(N log N)".+ *alegerea unui element pe post de **pivot** 
 + *parcurgerea vectorului din două părţi(de la stânga la pivot, de la dreapta la pivot, ambele în acelaşi timp) 
 + *interschimbarea elementelor care se află pe "**partea greşită**" a pivotului(mutăm la dreapta pivotului elementele mai mari, la stânga pivotului elementel mai mici) 
 + *divizarea algoritmului: după ce mutăm elementele pe "**partea corectă**" a pivotului, avem **2 subşiruri de sortat**, iar pivotul se află pe poziţia bună. 
 + 
 +<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 241: Linia 252:
 } }
 </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