Diferențe

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

Link către această vizualizare comparativă

--- laboratoare:laborator-08 [2017/02/23 13:30]
mihai.iacov [3.3 Insertion sort]
+++ laboratoare:laborator-08 [2017/04/20 20:53]
iulian.matesica [4. Exerciţii]
@@ Linia 28: / Linia 28: @@
 Folosim notaţia O(n) pentru a indica:
  *un număr de operaţii de ordinul lui n. În acest caz, spunem că avem "**complexitate de timp de ordinul lui n**"
- *o dimensiune de ordinul n pentru memoria alocată. În acest caz, spunem că avem "**complexitate de spaţiu de ordinul lui n**"
+ *o dimensiune de ordinul lui n pentru memoria alocată. În acest caz, spunem că avem "**complexitate de spaţiu de ordinul lui n**"
@@ Linia 59: / Linia 59: @@
  *Parcurgerea tabloului de la stânga spre dreapta se va repeta atât timp cât vor fi întâlnite
 elemente neordonate.
+{{ :laboratoare:bubble-sort-example-300px.gif?nolink |}}
 ===Implementare :===
@@ Linia 65: / Linia 67: @@
 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>
@@ Linia 94: / Linia 97: @@
 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**.
+{{ :laboratoare:selection-sort.gif?nolink |}}
 ===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.
  *Când partea nesortată nu mai are nici un element, algoritmul se opreste.
+{{ :laboratoare:insertion-sort-example-300px.gif?nolink |}}
 ===Implementare :===
@@ Linia 149: / Linia 155: @@
             aux = a[j]; //interschimbare
             a[j] = a[j - 1];
-            a[j--] = aux;
+            a[--j] = aux;
         }
     }
@@ Linia 155: / Linia 161: @@
 </file>
-====3.2 Merge sort====
+====3.4 Merge sort====
   * timp mediu: O(N log N)
@@ Linia 162: / Linia 168: @@
   * Stabil: DA
-====3.1 Quick sort====
+===Descriere :===
+În cazul sortării prin interclasare, vectorii care se interclasează sunt două secvenţe ordonate
+din acelaşi vector.
+Sortarea prin interclasare utilizează metoda **Divide et Impera**:
+ *se împarte vectorul în secvenţe din ce în ce mai mici, astfel încât fiecare secvenţă să fie
+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.
+{{ :laboratoare:merge-sort-example-300px.gif?nolink |}}
+===Implementare :===
+<file cpp>
+void mergeSort(int a[],int st, int m, int dr)
+{
+    int b[100];
+    int i, j, k;
+    i = 0; j = st;
+    // copiem prima jumatate a vectorului a in b
+    while (j <= m)
+        b[i++] = a[j++];
+    i = 0; k = st;
+    // copiem inapoi cel mai mare element la fiecare pas
+    while (k < j && j <= dr)
+        if (b[i] <= a[j])
+            a[k++] = b[i++];
+        else
+            a[k++] = a[j++];
+    // copiem elementele ramase daca mai exista
+    while (k < j)
+        a[k++] = b[i++];
+}
+void merge(int a[],int st, int dr)
+{
+    if (st < dr)
+    {
+        int m = (st+dr)/2;
+        merge(a,st, m);
+        merge(a,m+1, dr);
+        mergeSort(a,st, m, dr);
+    }
+}
+</file>
+====3.5 Quick sort====
   * timp mediu: O(N log N)
@@ Linia 168: / Linia 218: @@
   * memorie: O(log N)
   * Stabil: NU
+===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)".
+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 :===
+<file cpp>
+void qSort(int a[],int st,int dr)
+{
+    int temp,min,max,mijl;
+    mijl = a[st+(dr-st)/2]; //luam mijlocul intervalului
+    min = st; max = dr;
+    do
+    {
+        while(a[min] < mijl) min++;
+        while(a[max] > mijl) max--;
+        if(min <= max) //interschimbare
+        {
+            temp = a[min];
+            a[min++] = a[max];
+            a[max--] = temp;
+        }
+    }while(min <= max); //la fiecare pas sortam "mai bine" intervalul st-dr
+    //cand numai avem ce face schimbam intervalul
+    if(st < max) qSort(a,st,max); //crescator
+    if(dr > min) qSort(a,min,dr); //crescator
+}
+</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%%''.

Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Diferențe

Unelte pagină