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/20 21:19]
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 49: / Linia 49: @@
   * memorie: O(1)
   * Stabil: DA
+===Descriere :===
+Sortarea prin metoda bulelor se consideră drept una din cele mai puţin efective metode de
+sortare, dar cu un algoritm mai simplu.
+ *Ideea de bază a sortării prin metoda bulelor este în a parcurge tabloul, de la stânga spre dreapta,
+fiind comparate elementele alăturate **a[i] si a[i+1]**. Dacă vor fi găsite 2 elemente neordonate,
+valorile lor vor fi interschimbate.
+ *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 :===
+<file cpp>
+//sortare descrescatoare
+void bubble(int a[],int n)
+{
+    int i,schimbat,aux;
+    do {
+        schimbat = 0;
+        // parcurgem vectorul
+        for(i = 0; i < n-1; i++) {
+	    // daca valoarea i din vectorul a este mai mica decat cea de pe pozitia i+1
+            if (a[i] < a[i+1]) {
+                // interschimbare
+	        aux = a[i];
+		a[i] = a[i+1];
+		a[i+1] = aux;
+		schimbat = 1;
+	    }
+        }
+    } while(schimbat);
+}
+</file>
 ====3.2 Selection sort====
@@ Linia 55: / Linia 90: @@
   * timp la limită: O(N^2)
   * memorie: O(1)
-  * Stabil: NU
+  * Stabil: DA
+===Descriere :===
+Acest algoritm selectează, la fiecare pas i, cel mai mic element din vectorul nesortat(de la poziţia
+i până la n).Valoarea minimă găsită la pasul i este pusă în vector la poziţia i,facându-se
+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 :===
+<file cpp>
+void selectionSort(int a[],int n)
+{
+	int i,j,aux,min,minPoz;
+	for(i = 0; i < n - 1;i++)
+	{
+		minPoz = i;
+		min = a[i];
+		for(j = i + 1;j < n;j++) //selectam minimul
+		//din vectorul ramas( de la i+1 la n)
+		{
+			if(min > a[j]) //sortare crescatoare
+			{
+				minPoz = j; //pozitia elementului minim
+				min = a[j];
+			}
+		}
+		aux = a[i] ;
+		a[i] = a[minPoz]; //interschimbare
+		a[minPoz] = aux;
+	}
+}
+</file>
 ====3.3 Insertion sort====
@@ Linia 63: / Linia 130: @@
   * memorie: O(1)
   * Stabil: DA
-====3.2 Merge sort====
-====3.1 Quick sort====
+===Descriere :===
+Spre deosebire de alţi algoritmi de sortare, sortarea prin inserţie este folosită destul de des
+pentru sortarea tablourilor cu **număr mic de elemente**. De exemplu, poate fi folosit pentru a
+îmbunătăţi rutina de sortare rapidă.
+ *Sortarea prin inserţie seamană oarecum cu sortarea prin selecţie. Tabloul este împărţit
+imaginar în două părţi - o parte sortată şi o parte nesortată. La început, partea sortată conţine
+primul element al tabloului şi partea nesortată conţine restul tabloului.
+ *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 :===
+<file cpp>
+void insertionSort(int a[], int n)
+{
+    int i, j, aux;
+    for (i = 1; i < n; i++)
+    {
+        j = i;
+        while (j > 0 && a[j - 1] > a[j])
+        { //cautam pozitia pe care sa mutam a[i]
+            aux = a[j]; //interschimbare
+            a[j] = a[j - 1];
+            a[--j] = aux;
+        }
+    }
+}
+</file>
+====3.4 Merge sort====
+  * timp mediu: O(N log N)
+  * timp la limită: O(N log N)
+  * memorie: O(N)
+  * Stabil: DA
+===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)
+  * timp la limită: O(N^2)
+  * 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ă