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:44]
mihai.iacov [3.5 Quick 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 149: Linia 155:
             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 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 213: Linia 221:
 ===Descriere :=== ===Descriere :===
 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)". 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)".
 +
 +Algoritmul se bazează pe următorii paşi:
 + *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 237: 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