Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Ești aici: Structuri de date și algoritmi » Laboratoare » Laborator 02: Algoritmi de sortare 1
Traseu:
laboratoare:laborator-02

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-02 [2017/03/02 20:51]
iulian.matesica 		laboratoare:laborator-02 [2018/02/25 21:32]
mihai.iacov
Linia 1: Linia 1:
-====== Laborator 02: Liste ====== +====== Laborator 02: Algoritmi de sortare 1 ======
-\\ +
-=====1 Obiectivele laboratorului===== +
-*Înțelegerea conceptului de funcționare și implementarea unor liste dublu înlănțuite și circulare +
-*Implementarea unor funcții individuale de lucru cu aceste structuri de date. +
-\\+
  
-=====2 Ce este o listă?===== +=====1. Obiectivele laboratorului=====
-====2.1 Definiție==== +
-Listele sunt cele mai bune și cele mai simple exemple a unei structuri de date dinamice care folosește pointeri +
-la implementarea sa.în mod esențial, trebuie înțeles că listele funcționează ca un vector care se poate mări sau +
-micșora după nevoie, din orice punct al mulțimii sale de elemente.+
  
-{{ :laboratoare:array_vs_list.png?400 |}}+Propunem studierea următorilor algoritmi de sortare: 
 + * Bubble Sort 
 + * Selection Sort 
 + * Insertion Sort 
 + * Merge Sort 
 + * Quick Sort
  
-Avantaje ale utilizării listelor: +=====2. Introducere=====
-*Elementele pot fi adăugate sau șterse din mijlocul listei +
-*Nu trebuie definită o mărime inițială, iar memoria se alocă pe rând, odată cu fiecare element adăugat+
  
-Definirea nodului unei liste:+====2.1 Caracterizarea unui algoritm==== 
 + 
 +Numim **sortare** orice aşezare(sau - mai clar - **reaşezare**) a unor elemente date în aşa fel încât, după aşezare, să existe o  **ordine completă** în funcţie de un atribut(numit **cheie**) al elementelor. 
 + 
 +Pentru a exista o **ordine completă**, trebuie să alegem o **relaţie** pe care vrem sa o impunem. Dacă relaţia este valabilă între **oricare două elemente** pentru care **primul** element **este** aşezat **la stânga** celui de-al doilea, atunci avem o **ordine completă**. 
 + 
 +Exemplu: dacă alegem drept cheie un atribut **număr întreg** şi relaţia **mai mic sau egal**(<=), obţinem **ordinea crescătoare**. 
 + 
 +Vom descrie un algoritm de sortare prin: 
 + *timp mediu - timpul de execuţie la care ne aşteptăm, **în medie**, pentru sortare 
 + *timp la limită- timpul de execuţie pentru **cel mai rău** caz posibil 
 + *memorie - memoria **maximă** de care are nevoie algoritmul pentru sortare(**excludem memoria deja alocată** înainte de algoritm -> vectorul efectiv ce va fi sortat) 
 + *stabilitate - un algoritm stabil păstrează ordinea în care apar două elemente cu aceeaşi cheie(atributul după care sortăm) 
 + 
 +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 lui n pentru memoria alocată. În acest caz, spunem că avem "**complexitate de spaţiu de ordinul lui n**" 
 + 
 + 
 +====2.2 Metodele de sortare folosite==== 
 + 
 +Fiecare algoritm se bazează pe o metodă de sortare: 
 + *Bubble sort - interschimbare 
 + *Selection sort - selecţie 
 + *Insertion sort - inserare 
 + *Merge sort - interclasare 
 + *Quick sort - partiţionare 
 + 
 + 
 +=====3. Algoritmii===== 
 + 
 +====3.1 Bubble sort==== 
 + 
 +  * timp mediu: O(N^2) 
 +  * timp la limită: O(N^2) 
 +  * 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> <file cpp>
-typedef struct { +//sortare descrescatoare 
-     int val; +void bubble(int a[],int n) 
-     node *next; +{ 
-} node_t;+    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> </file>
  
-====2.2 Clasificare==== +====3.2 Selection sort====
-* **Liste simplu înlănțuite** - Elementele au o singură legătură către următorul element introdus, iar ultimul +
-element pointează către NULL.+
  
-{{ :laboratoare:simplelist.png?500 | Liste simplu înlănțuite}}+  * timp mediu: O(N^2) 
 +  * timp la limită: O(N^2) 
 +  * memorie: O(1) 
 +  * 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 |}}
  
-* **Liste dublu înlănțuite** - Elementele au dublă legătură către precedentul și antecedentul, capul listei pointând +===Implementare :=== 
-spre NULL și ultimul element de asemenea+<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>
  
-{{ :laboratoare:doublelist.jpg?500 |}}+====3.3 Insertion sort====
  
-* **Liste circulare** - Pot fi simplu sau dublu înlănțuite cu proprietatea că ultimul element pointează spre primul.+  * timp mediu: O(N^2) 
 +  * timp la limită: O(N^2) 
 +  * memorie: O(1) 
 +  * Stabil: DA
  
-{{ :laboratoare:circularlist.png?500 |#Poza lista circulare#}}+===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.
  
-====2.3 Operații cu liste:==== +{{ :laboratoare:insertion-sort-example-300px.gif?nolink |}}
-*Adăugare la începutul listei +
-*Adăugare la sfârsitul listei +
-*Adăugarea înainte sau după un element dat +
-*Ștergerea capului de listă +
-*Ștergerea unui element oarecare din listă+
  
 +===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.Exerciții propuse pentru laborator===== +====3.4 Merge sort====
-1. Creați o listă circulară,dublu inlănțuită cu 6 angajați ai unei companii, care să conțină următoarele referințe: nume, nr de telefon, post. +
-  * Scrieți funcțiile care să scrie urmatoarele:\\ +
-  * Să introducă un nou angajat după al treilea.\\ +
-  * Să introducă un nou angajat inainte de cel care e "mecanic".\\ +
-  * Să steargă angajatul cu un anumit număr de telefon introdus.\\+
  
-2. Să se creeze o listă liniara simplu inlantuita care contine elemente intregi citite dintr-ul fisier text. +  * timp mediu: O(N log N) 
-Se citeste apoi o valoare intreaga x. Sa se stearga primul nod care contine valoarea x. +  * timp la limită: O(N log N) 
-Fișierul se va da ca parametru în linia de comandă.+  * memorie: O(N) 
 +  * Stabil: DA
  
-3.Sa se construiasca o lista liniara simplu inlantuita cu elemente numere intregi. Să se afișeze și apoi să se stearga din lista elementele pare. +===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**:
  
-=====4. Exercitii Liste ===== + *se împarte vectorul în secvenţe din ce în ce mai mici, astfel încât fiecare secvenţă să fie 
-Pentru laboratorul de liste inlantuite vom porni de la o arhiva cu un schelet de laborator. Nu veti scrie codul de la zero ci veti implementa cateva functii in fisierul ''%%list.c%%''.+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.
  
-Descarcati arhiva de aici si dezarhivati-o. Puteti folosi utilitarul ''%%wget%%'' pentru descarcare si utilitarul ''%%unzip%%' pentru dezarhivare. +{{ :laboratoare:merge-sort-example-300px.gif?nolink |}}
-<code bash> +
-student@sda-ab-vm:~/Documents$ wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab1-skel.zip +
---2017-03-02 20:45:55--  http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab1-skel.zip +
-Resolving elf.cs.pub.ro (elf.cs.pub.ro)... 141.85.227.116 +
-Connecting to elf.cs.pub.ro (elf.cs.pub.ro)|141.85.227.116|:80... connected. +
-HTTP request sent, awaiting response... 200 OK +
-Length: 2368 (2,3K) [application/zip] +
-Saving to: ‘lab1-skel.zip’+
  
-lab1-skel.zip       100%[===================>]   2,31K  --.-KB/s    in 0s      +===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>
  
-2017-03-02 20:45:56 (4,78 MB/s) - ‘lab1-skel.zip’ saved [2368/2368]+====3.5 Quick sort====
  
-student@sda-ab-vm:~/Documents$ ls +  * timp mediu: O(N log N) 
-lab1-skel.zip +  * timp la limită: O(N^2) 
-student@sda-ab-vm:~/Documents$ unzip lab1-skel.zip +  * memorie: O(log N) 
-Archive:  lab1-skel.zip +  * Stabil: NU
-  inflating: list.c                   +
-  inflating: list.h                   +
-  inflating: Makefile +
-student@sda-ab-vm:~/Documents$ make +
-gcc list.c -o list -std=gnu99 +
-student@sda-ab-vm:~/Documents$ make run +
-</code>+
  
-Pentru compilare folositi comanda ''%%make%%''. Pentru rulare puteti folosi fie **''%%./list%%''** fie comanda ''%%make run%%''.+===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 =====
  
-====Probleme opţionale - de interviu====+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.
  
-1. Se dă o listă simplu înlănţuită(primiţi doar un pointer către primul element). Verificaţi dacă lista conţine o buclă. (o listă simplu înlănţuită conţine o buclă => niciun element nu are legătura NULL)+E1. Implementaţi un algoritm(dintre Bubble, Insertion şi Selection) pentru sortarea unui vector cu n cuvinte de maxim 4 litere fiecare.
  
-2. Se dau două liste(pentru fiecare listă - pointer către primul element) în formă de Y(listele se intersectează, ultimele k elemente sunt comune). Aflaţi valoarea lui k.+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).
  
-3. Se dă o listă  cu 2n+1 elemente, fiecare element conţine câte un întreg. Toate valorile întregi apar de două ori în listă, excepţie facând una singură. Aflaţi acea valoare.+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).
  
-====== Extra: Hashtable(tabela de dispersie)======+<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>
  
-=====1 Introducere=====+Puteţi utiliza următorul model pentru exerciţiile propuse: {{ :laboratoare:scheletsortare.zip |}}
  
-(De urmărit ideea din introducere şi funcţia de indexare)+===== 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. 
  
-====1.1 Poveste====+=== Linux=== 
 +Puteti folosi utilitarul ''%%wget%%'' pentru descarcare si utilitarul ''%%unzip%%'' pentru dezarhivare.
  
-===Să presupunem urmatoarele detalii dintr-un caz real:===+  * ''%%wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab8_sortari-skel.zip%%'' 
 +  * ''%%unzip lab8_sortari-skel.zip%%''
  
- **Situaţia**: -Într-o bibliotecă sunt foarte multe cărţi şi, deşi spaţiul nu reprezintă o problemă, angajaţii nu dispun de suficient timp pentru a ordona toate cărţile după titlu(în ordine alfabetică).+Pentru compilare folositi comanda ''%%make%%''. Pentru rulare puteti folosi comanda ''%%make run%%'' sau ''%%./sort%%''.
  
- **Problema**: -Ei vor să găsească o metodă de a pune cărţile pe rafturi în aşa fel in 
laboratoare/laborator-02.txt · Ultima modificare: 2018/02/25 22:02 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